Theorem 5.4 — Gaussian LWE to uniform-zero-fiber LWE: , and the hardness transfer
ProvedInfoLossLAR.WorstCase.theorem_5_4cryptographylearning-with-errorsp2o-gran-per-chapterp2o-plan-bookp2o-v1reduction
Fix an efficiently computable public parameter family (with Gaussian width in pp) that admits fixed-order Gaussian T-AFTs (Definition 5.3).
(1) For every integer , every uniform QPT distinguisher on classical sample tables and every positive polynomially bounded block count , there is a uniform QPT reduction that runs once on a classically prepared table, and a threshold , with
(2) If Gaussian decisional LWE is hard against uniform QPT distinguishers on classical inputs for every positive polynomial block count (the advantage is negligible), then so is uniform-zero-fiber LWE for this family.
Differences from the source:
- reading: "uniform QPT distinguisher/reduction" →
IsQPT(uniform Clifford+T circuit families on binary-coded inputs); reason: the paper names no model - reading: "uses input blocks and one call to " →
CallsOnce B D; reason: structural reading of "one call" - encoding: "polynomially bounded block count" → positive and polynomially bounded; reason: a block count is (Definition 2.10)
- reading: "Gaussian width included in pp" → a positive rational in pp; reason: pp is finite binary data
Preamble
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_QPT import Definitions.Def_InfoLossLAR_WorstCase_Laws import Definitions.Def_InfoLossLAR_WorstCase_Family set_option autoImplicit false open QAlgorithms.Complexity
Formal statement
namespace InfoLossLAR.WorstCase
/-- Theorem 5.4 (Gaussian LWE to uniform-zero-fiber LWE), p. 24, for an efficiently computable
family that admits fixed-order Gaussian T-AFTs. (1) For every integer `c ≥ 1`, every uniform QPT
distinguisher `D` and every positive, polynomially bounded block count `t`, there is a uniform
QPT reduction `B` that runs `D` once on a classically prepared input, and a threshold `λ₀`, with
`Adv^{UZF-LWE}_D(λ, t) ≤ Adv^{Gauss-LWE}_B(λ, t) + t λ^{−c}` for all `λ ≥ λ₀`. (2) If Gaussian
decisional LWE is hard against uniform QPT distinguishers for every positive polynomial block
count, then so is uniform-zero-fiber LWE for this family. -/
theorem theorem_5_4 (F : RoundingFamily) (hF : F.Efficient)
(hAFT : F.AdmitsFixedOrderGaussianAFT) :
(∀ c : ℕ, 1 ≤ c → ∀ D : Family, IsQPT D →
∀ t : ℕ → ℕ, (∀ lam, 1 ≤ t lam) → PolyBoundedFn t →
∃ B : Family, IsQPT B ∧ CallsOnce B D ∧
∃ lam₀ : ℕ, ∀ lam ≥ lam₀,
F.advUZF D lam (t lam) ≤
F.advGauss B lam (t lam) + (t lam : ℝ) * (lam : ℝ) ^ (-(c : ℝ))) ∧
((∀ B : Family, IsQPT B → ∀ t : ℕ → ℕ, (∀ lam, 1 ≤ t lam) → PolyBoundedFn t →
Negligible fun lam => F.advGauss B lam (t lam)) →
∀ D : Family, IsQPT D → ∀ t : ℕ → ℕ, (∀ lam, 1 ≤ t lam) → PolyBoundedFn t →
Negligible fun lam => F.advUZF D lam (t lam)) := 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. 24, Theorem 5.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.