Theorem 4.2 — uniform-zero-fiber LWE to decisional LAR:
ProvedInfoLossLAR.WorstCase.theorem_4_2cryptographylearning-with-errorslearning-with-roundingp2o-gran-per-chapterp2o-plan-bookp2o-v1reduction
Fix an efficiently computable public parameter family as in §3.1 and the error law . For every uniform QPT distinguisher on classical sample tables and every positive integer-valued sample count bounded by a polynomial, there is a uniform QPT distinguisher , which runs once on a classically prepared table, such that for every security parameter
Here receives LWE blocks with .
This is the first of the two classical reductions from Gaussian LWE to decisional LAR.
Differences from the source:
- reading: "uniform QPT distinguisher" → a uniform, well-formed, polynomially bounded Clifford+T circuit family on the binary code of ; reason: the paper names no model
- reading: "using input blocks and one call to " →
CallsOnce B D: equals running once on a classical polynomial-time preprocessing of followed by a classical polynomial-time post-processing of its bit; reason: structural reading of "one call" - encoding: pp of a §3.1 family → also lists a rational width (Definition 5.3's augmentation); reason: one family type serves §§3–5; an extra public entry changes no instance
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 4.2 (From uniform-zero-fiber LWE to decisional LAR), p. 22: for an efficiently
computable public parameter family and `χ = U(F_{T,0})`, for every uniform QPT distinguisher `D`
and every positive, polynomially bounded sample count `t`, there is a uniform QPT distinguisher
`B` that runs `D` once on a classically prepared input, with
`Adv^{dLAR}_D(λ, t) ≤ q · Adv^{LWE}_B(λ, t) + q^{−N}` for every `λ ≥ 1`. -/
theorem theorem_4_2 (F : RoundingFamily) (hF : F.Efficient) (D : Family) (hD : IsQPT D)
(t : ℕ → ℕ) (ht : ∀ lam, 1 ≤ t lam) (htp : PolyBoundedFn t) :
∃ B : Family, IsQPT B ∧ CallsOnce B D ∧
∀ lam : ℕ, 1 ≤ lam →
F.advLAR D lam (t lam) ≤
(F.q lam : ℝ) * F.advUZF B lam (t lam) + ((F.q lam : ℝ) ^ F.N 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. 22, Theorem 4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.