Theorem 9.9 — the fixed family admits fixed-order Gaussian T-AFTs with accuracy
ProvedInfoLossLAR.WorstCase.theorem_9_9discrete-gaussianlatticeslearning-with-roundingp2o-gran-per-chapterp2o-plan-bookp2o-v1
Consider the family of §9.9: , , , the least prime , , and , of Definition 6.3. For every calibration order there are a constant and a nonnegative negligible function , both depending only on , such that for every integer with and every numerical budget with an integer (so ), there is a uniform PPT sampler whose every execution returns , such that for all sufficiently large , with independent,
and which satisfies Definition 5.3: the same distance is at most for all sufficiently large .
Differences from the source:
- reading: "for the fixed calibration order chosen above" (, §9.10) and the constants , → for every , constants depending only on , valid for every with ; reason: the subscript and Proposition 9.6 fix them by alone
- reading: "" (§9.10) → every budget with integer ; reason: §9.10 chooses one budget below ¼L^{−(c+2)} without pinning it; e = c is the printed bound ¼L^{−(c+2)} itself, and every smaller inverse power of L is covered as well, so the statement contains the source's choice
- reading: "uniform PPT sampler" →
IsPPTAffineSampler: one classical polynomial-time map from (coins, code of ) to the code of , with polynomially many coins; reason: the paper names no model; reading only , pp and coins is the source independence - encoding: and → and over ; reason: the same law, as are integral
- encoding: the label in → a vector of ; reason:
Preamble
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_QPT import Definitions.Def_InfoLossLAR_WorstCase_Rounding import Definitions.Def_InfoLossLAR_WorstCase_Laws import Definitions.Def_InfoLossLAR_WorstCase_Family set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase
/-- Theorem 9.9 (Constructive fixed-order Gaussian AFT), p. 59, for the fixed family of §9.9
(`L = λ + 2`, `N = λ`, `σ = L`, `q` the least prime `≥ 2^{16} L^{64}`,
`d = qL^{96} + 2L^{128}`, `T` and `P = 1ᵀ` of Definition 6.3). For every calibration order `R`
there are a constant `C_R > 0` and a nonnegative negligible function `negl_R` such that for every
integer `c ≥ 1` with `R ≥ 4c + 267` (§9.10) and every numerical budget
`ε_num = (1/4) L^{−(e+2)}` with an integer `e ≥ c` (so `ε_num ≤ (1/4) L^{−(c+2)}`, §9.10) there is
a uniform classical PPT sampler
`Sample_c(1^λ, pp) → (Q, β) ∈ ℤ^{d×d} × ℤ^d` whose every output has `Q mod q ∈ GL_d(𝔽_q)`, such
that for all sufficiently large `λ`, with `x ← D_{ℤ^d,σ}` independent,
`Δ(L(Qx + β mod q), U(F_{T,0})) ≤ C_R q L^{−(R+1)/4} + negl_R(L) + ε_num`,
and which satisfies Definition 5.3: this distance is at most `λ^{−c}` for all large `λ`. -/
theorem theorem_9_9 (R : ℕ) :
∃ C_R : ℝ, 0 < C_R ∧ ∃ negl_R : ℕ → ℝ, Negligible negl_R ∧
∀ c : ℕ, 1 ≤ c → 4 * c + 267 ≤ R → ∀ e : ℕ, c ≤ e →
∃ (m : Polynomial ℕ)
(S : (lam : ℕ) → (Fin (m.eval lam) → Bool) →
Matrix (Fin (famd lam)) (Fin (famd lam)) ℤ × (Fin (famd lam) → ℤ)),
IsPPTAffineSampler famInput famd m S ∧
(∀ (lam : ℕ) (ρ : Fin (m.eval lam) → Bool), IsUnit (matModq (famq lam) (S lam ρ).1).det) ∧
(∃ lam₀ : ℕ, ∀ lam ≥ lam₀,
sdist (transportLaw (S lam) (chiG (famq lam) (famd lam) (famσ lam)))
(unifZeroFiber (famLabel lam)) ≤
C_R * (famq lam : ℝ) * (famL lam : ℝ) ^ (-((R : ℝ) + 1) / 4) +
negl_R (famL lam) + (1 / 4) * (famL lam : ℝ) ^ (-((e : ℝ) + 2))) ∧
(∃ lam₀ : ℕ, ∀ lam ≥ lam₀,
sdist (transportLaw (S lam) (chiG (famq lam) (famd lam) (famσ lam)))
(unifZeroFiber (famLabel lam)) ≤ (lam : ℝ) ^ (-(c : ℝ))) := 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. 58 §§9.9–9.10, p. 59, Theorem 9.9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.