Lemma 5.2 — a T-AFT keeps exactly uniform and independent of the transported error
ProvedInfoLossLAR.WorstCase.lemma_5_2learning-with-errorsp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1probability
Let be an odd prime, a rounding matrix with chosen Smith matrices and , and a law on . Let the affine data be drawn from a uniform coin in a finite nonempty set , with for every , and suppose the transport is -accurate (): for independent. Sample , and independently, and set , . Then
i.e. is exactly uniform and independent of ; ; and for independent of , .
Differences from the source:
- generalization: a pair of uniform classical PPT algorithms → any function of a uniform coin in any finite nonempty set; reason: the lemma uses only invertibility and the accuracy bound; a PPT sampler with coins is the case
- encoding: " exactly uniform and independent of " → the joint point masses equal times the law of ; reason: the definition of independence with a uniform marginal
- encoding: → the affine map ; reason: Definition 5.1's affine-evaluation requirement
Preamble
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_QPT import Definitions.Def_InfoLossLAR_WorstCase_Rounding import Definitions.Def_InfoLossLAR_WorstCase_Laws set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase
/-- Lemma 5.2 (Basic properties of T-AFT), p. 23. The sampler draws `(Q, β) = samp(ρ)` from a
uniform coin `ρ ∈ Ω`, every output has `Q mod q ∈ GL_d(𝔽_q)`, and `Δ(L(Eval(Q, β, e)),
U(F_{T,0})) ≤ δ` for `e ← χ` independent. With `A ← U(𝔽_q^{d×N})`, `e ← χ` and `ρ` independent,
`A' = QA` and `e' = Eval(Q, β, e)`: (1) the joint law of `(A', e')` is
`U(𝔽_q^{d×N}) ⊗ L(e')` (`A'` exactly uniform and independent of `e'`); (2)
`Δ(L(e'), U(F_{T,0})) ≤ δ`; (3) for `u ← U(𝔽_q^d)` independent of `(A, ρ)`, the law of
`(QA, Eval(Q, β, u))` is `U(𝔽_q^{d×N}) × U(𝔽_q^d)`. -/
theorem lemma_5_2 (q r d N : ℕ) [Fact q.Prime] (hq2 : q ≠ 2) (T : Matrix (Fin d) (Fin d) ℤ)
(S : SmithData q r d T) (hℓ : r < d)
(χ : (Fin d → ZMod q) → ℝ) (hχ0 : ∀ e, 0 ≤ χ e) (hχ1 : ∑ e, χ e = 1)
(Ω : Type) [Fintype Ω] [Nonempty Ω]
(samp : Ω → Matrix (Fin d) (Fin d) ℤ × (Fin d → ℤ))
(δ : ℝ) (hδ0 : 0 ≤ δ) (hδ1 : δ ≤ 1)
(hinv : ∀ ρ, IsUnit (matModq q (samp ρ).1).det)
(hfib : sdist (transportLaw samp χ) (unifZeroFiber S.fT) ≤ δ) :
(∀ (A' : Matrix (Fin d) (Fin N) (ZMod q)) (x' : Fin d → ZMod q),
(avg fun ρ : Ω => avg fun A : Matrix (Fin d) (Fin N) (ZMod q) =>
∑ e : Fin d → ZMod q,
if matModq q (samp ρ).1 * A = A' ∧ evalAffine (samp ρ).1 (samp ρ).2 e = x'
then χ e else 0) =
(Fintype.card (Matrix (Fin d) (Fin N) (ZMod q)) : ℝ)⁻¹ * transportLaw samp χ x') ∧
sdist (transportLaw samp χ) (unifZeroFiber S.fT) ≤ δ ∧
(∀ (A' : Matrix (Fin d) (Fin N) (ZMod q)) (x' : Fin d → ZMod q),
(avg fun ρ : Ω => avg fun A : Matrix (Fin d) (Fin N) (ZMod q) =>
avg fun u : Fin d → ZMod q =>
if matModq q (samp ρ).1 * A = A' ∧ evalAffine (samp ρ).1 (samp ρ).2 u = x'
then (1 : ℝ) else 0) =
((Fintype.card (Matrix (Fin d) (Fin N) (ZMod q)) : ℝ) * (q : ℝ) ^ d)⁻¹) := 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. 23, Lemma 5.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.