Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 10.1 — a decisional LAR distinguisher for the fixed family yields quantum worst-case GapSVPγ\mathrm{GapSVP}_\gammaGapSVPγ​ and SIVPγ\mathrm{SIVP}_\gammaSIVPγ​ solvers, γ=O~(q)\gamma=\tilde O(q)γ=O~(q)

Proved
InfoLossLAR.WorstCase.corollary_10_1

by Shuze Chen · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographylatticeslearning-with-roundingp2o-gran-per-chapterp2o-plan-bookp2o-v1quantum-computingreduction

Consider the fixed public family of §9.9: N=λN=\lambdaN=λ, σ=λ+2\sigma=\lambda+2σ=λ+2, q=q(λ)q=q(\lambda)q=q(λ) the least prime ≥216(λ+2)64\ge2^{16}(\lambda+2)^{64}≥216(λ+2)64, d=q(λ+2)96+2(λ+2)128d=q(\lambda+2)^{96}+2(\lambda+2)^{128}d=q(λ+2)96+2(λ+2)128, the rounding matrix TTT and quotient encoding P=1⊤P=\mathbf 1^\topP=1⊤ of Definition 6.3, so that the decisional LAR experiment draws s←U(FqN)s\leftarrow U(\mathbb F_q^N)s←U(FqN​), Mi←U(Fqd×N)M_i\leftarrow U(\mathbb F_q^{d\times N})Mi​←U(Fqd×N​) and labels fT(Mis)=∑j⌊(T[Mis]q)j/q⌋ mod qf_T(M_is)=\sum_j\lfloor(T[M_is]_q)_j/q\rfloor\bmod qfT​(Mi​s)=∑j​⌊(T[Mi​s]q​)j​/q⌋modq.

There are constants C,k∈NC,k\in\mathbb NC,k∈N, fixed before the adversary, such that with

γ(λ)=C⋅q(λ)⋅(log⁡2(λ+2))k(γ=O~(Nq/σ)=O~(q)),\gamma(\lambda)=C\cdot q(\lambda)\cdot(\log_2(\lambda+2))^k\qquad(\gamma=\tilde O(Nq/\sigma)=\tilde O(q)),γ(λ)=C⋅q(λ)⋅(log2​(λ+2))k(γ=O~(Nq/σ)=O~(q)),

for every uniform QPT distinguisher DDD on classical inputs, every positive polynomially bounded sample count ttt, every c∈Nc\in\mathbb Nc∈N and every infinite set SSS of security parameters with AdvDdLAR(λ,t(λ))≥λ−c\mathrm{Adv}^{\mathrm{dLAR}}_D(\lambda,t(\lambda))\ge\lambda^{-c}AdvDdLAR​(λ,t(λ))≥λ−c for all λ∈S\lambda\in Sλ∈S, there are a uniform QPT algorithm that solves worst-case GapSVPγ\mathrm{GapSVP}_\gammaGapSVPγ​ and a uniform QPT algorithm that solves worst-case SIVPγ\mathrm{SIVP}_\gammaSIVPγ​ in dimension N=λN=\lambdaN=λ, for every λ∈S\lambda\in Sλ∈S.

This is the paper's main reduction (Theorem 1.1): quantum worst-case hardness of GapSVPO~(q)\mathrm{GapSVP}_{\tilde O(q)}GapSVPO~(q)​ or SIVPO~(q)\mathrm{SIVP}_{\tilde O(q)}SIVPO~(q)​ on infinitely many dimensions implies decisional LAR hardness for every polynomial sample count.

Differences from the source:

  • reading: "uniform QPT distinguisher", "uniform quantum polynomial-time algorithms" → IsQPT/IsMQPT: uniform Clifford+T circuit families (no advice, fixed gate set) on binary-coded classical inputs, Born-rule measurement of the output wires; reason: the paper names no model
  • reading: "approximation factor O~(Nq/σ)=O~(q)\tilde O(Nq/\sigma)=\tilde O(q)O~(Nq/σ)=O~(q)" → ∃C,k\exists C,k∃C,k fixed before DDD, γ=C q (log⁡2(λ+2))k\gamma=C\,q\,(\log_2(\lambda+2))^kγ=Cq(log2​(λ+2))k; reason: O~\tilde OO~ is a constant times a polylogarithmic factor; a larger γ\gammaγ only makes both problems easier
  • reading: "nonnegligible advantage" and "guaranteed only on infinitely many security parameters … succeed on those parameters" → for every ccc and every infinite SSS with advantage ≥λ−c\ge\lambda^{-c}≥λ−c on SSS, solvers succeeding at every λ∈S\lambda\in Sλ∈S; reason: not negligible means ≥λ−c\ge\lambda^{-c}≥λ−c infinitely often; the algorithms do not depend on λ\lambdaλ
  • reading: worst-case GapSVPγ_\gammaγ​/SIVPγ_\gammaγ​ → nonsingular integer bases in binary, Euclidean norm, rational gap parameter δ>0\delta>0δ>0, success probability ≥23\ge\frac23≥32​ on every instance, SIVP output = code of NNN integer lattice vectors at the start of the output string; reason: standard conventions of the cited [Reg05], not restated by the paper
  • encoding: security parameters → λ≥1\lambda\ge1λ≥1 for λ∈S\lambda\in Sλ∈S; reason: §3.1 indexes families by λ≥1\lambda\ge1λ≥1
  • encoding: the third sentence (worst-case hardness implies dLAR hardness) → not a separate clause; reason: it is the contrapositive of the stated implication
  • encoding: pp of the fixed family → the code of (q,N,d,σ)(q,N,d,\sigma)(q,N,d,σ); reason: TTT and PPP are determined by (q,d)(q,d)(q,d)
Preamble
import Mathlib
import Definitions.Def_InfoLossLAR_WorstCase_QPT
import Definitions.Def_InfoLossLAR_WorstCase_Laws
import Definitions.Def_InfoLossLAR_WorstCase_Family
import Definitions.Def_InfoLossLAR_WorstCase_LatticeProblems

set_option autoImplicit false

open QAlgorithms.Complexity
Formal statement
namespace InfoLossLAR.WorstCase

/-- Corollary 10.1 (Worst-case foundation for decisional LAR), p. 60, for the fixed family of
§9.9 (`N = λ`, `σ = λ + 2`, `q` the least prime `≥ 2^{16}(λ + 2)^{64}`,
`d = q(λ + 2)^{96} + 2(λ + 2)^{128}`, `T` and `P = 1ᵀ` of Definition 6.3). There are constants
`C, k ∈ ℕ`, fixed before the adversary, such that with `γ(λ) = C · q(λ) · (log₂(λ + 2))^k`
(`γ = Õ(Nq/σ) = Õ(q)`): for every uniform QPT distinguisher `D`, every positive polynomially
bounded sample count `t`, every `c` and every infinite set `S` of security parameters on which
`Adv^{dLAR}_D(λ, t(λ)) ≥ λ^{−c}`, there are a uniform QPT algorithm that solves worst-case
GapSVP_γ and a uniform QPT algorithm that solves worst-case SIVP_γ in dimension `N = λ`, for
every `λ ∈ S`. -/
theorem corollary_10_1 :
    ∃ C k : ℕ, ∀ D : Family, IsQPT D →
      ∀ t : ℕ → ℕ, (∀ lam, 1 ≤ t lam) → PolyBoundedFn t →
        ∀ c : ℕ, ∀ S : Set ℕ, S.Infinite → (∀ lam ∈ S, 1 ≤ lam) →
          (∀ lam ∈ S, (lam : ℝ) ^ (-(c : ℝ)) ≤ famAdvLAR D lam (t lam)) →
            (∃ A : Family, IsQPT A ∧ ∀ lam ∈ S,
              SolvesGapSVP A (famN lam)
                ((C : ℝ) * (famq lam : ℝ) * Real.logb 2 ((lam : ℝ) + 2) ^ k)) ∧
            (∃ A : MFamily, IsMQPT A ∧ ∀ lam ∈ S,
              SolvesSIVP A (famN lam)
                ((C : ℝ) * (famq lam : ℝ) * Real.logb 2 ((lam : ℝ) + 2) ^ k)) := 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. 60, Corollary 10.1 (with §9.9, p. 58, and Appendix I.1, pp. 132–133)
Human review
  • Endorsed by Community (Bot) · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me