Lemma 4.1 — the zero-fiber decomposition is a bijection
ProvedInfoLossLAR.WorstCase.lemma_4_1learning-with-roundingp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be an odd prime and a rounding matrix with chosen Smith matrices and (§3.1). The zero-fiber decomposition map
is a bijection, and its inverse is .
Consequently a uniform splits into an independent uniform zero-fiber residual and a uniform label; this is the step that turns uniform-zero-fiber LWE samples into LAR samples (Theorem 4.2).
Differences from the source:
- encoding: "its inverse is " → for all and : ; reason: equivalent formulation of the inverse
Preamble
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_Rounding set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase
/-- Lemma 4.1 (Zero-fiber decomposition), p. 21: with `q` an odd prime and `ℓ = d − r ≥ 1`, the
map `Φ_T : F_{T,0} × 𝔽_q^ℓ → 𝔽_q^d`, `(e, y) ↦ e + Jy`, is a bijection, and its inverse is
`x ↦ (x − J f_T(x), f_T(x))`. -/
theorem lemma_4_1 (q r d : ℕ) [Fact q.Prime] (hq2 : q ≠ 2) (T : Matrix (Fin d) (Fin d) ℤ)
(S : SmithData q r d T) (hℓ : r < d) :
Function.Bijective
(fun p : S.zeroFiber × (Fin (d - r) → ZMod q) => (p.1 : Fin d → ZMod q) + S.J.mulVec p.2) ∧
∀ (x : Fin d → ZMod q) (p : S.zeroFiber × (Fin (d - r) → ZMod q)),
(p.1 : Fin d → ZMod q) + S.J.mulVec p.2 = x ↔
((p.1 : Fin d → ZMod q) = x - S.J.mulVec (S.fT x) ∧ p.2 = S.fT x) := by sorry
end InfoLossLAR.WorstCase
Source
Chen Qian, Information Loss Is All You Need: TC⁰ Pseudorandomness from Worst-Case Lattices, arXiv:2611.05136 (held version, sha256 2ebdfbf3…), p. 21, Lemma 4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.