Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Fixed-family Gaussian LWE to quantum worst-case GapSVP and SIVP

Proved
InfoLossLAR.WorstCase.fixed_family_gaussian_lwe_worst_case

by BoomShaKaLaaaKa · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographylatticeslearning-with-roundingquantum-computingreduction

For the fixed public family of Section 9.9, there exist constants C,k∈NC,k\in\mathbb NC,k∈N, with C≥1C\ge1C≥1, satisfying the following statement. Let BBB be a uniform QPT Gaussian block-LWE distinguisher, let ttt be a positive polynomially bounded block-count function, let b∈Nb\in\mathbb Nb∈N, and let SSS be an infinite set of positive security parameters. Suppose that, for all sufficiently large λ∈S\lambda\in Sλ∈S,

Adv⁡BGauss-LWE(λ,t(λ))≥λ−b,\operatorname{Adv}^{\mathrm{Gauss\text{-}LWE}}_B(\lambda,t(\lambda))\ge\lambda^{-b},AdvBGauss-LWE​(λ,t(λ))≥λ−b,

where the block error distribution is DZd(λ),σ(λ) mod q(λ)D_{\mathbb Z^{d(\lambda)},\sigma(\lambda)}\bmod q(\lambda)DZd(λ),σ(λ)​modq(λ) and the distinguisher receives the fixed family's public parameters.

There exist uniform quantum polynomial-time algorithms solving worst-case GapSVPγ(λ)\mathrm{GapSVP}_{\gamma(\lambda)}GapSVPγ(λ)​ and SIVPγ(λ)\mathrm{SIVP}_{\gamma(\lambda)}SIVPγ(λ)​, respectively, in dimension N(λ)=λN(\lambda)=\lambdaN(λ)=λ, for every λ∈S\lambda\in Sλ∈S, where

γ(λ)=Cq(λ)(log⁡2(λ+2))k.\gamma(\lambda)=Cq(\lambda)(\log_2(\lambda+2))^k.γ(λ)=Cq(λ)(log2​(λ+2))k.

The algorithms satisfy the published worst-case success requirements on every nonsingular integer-basis instance. The constants C,kC,kC,k are fixed before B,t,b,SB,t,b,SB,t,b,S.

This is the Gaussian-LWE interface to the quantum worst-case lattice reduction, independent of LAR and affine fiber transport.

Formalization Note. The hypothesis only requires advantage eventually on SSS, whereas the conclusion includes all positive dimensions in SSS. Finitely many exceptional dimensions are included using exact fixed-dimensional lattice algorithms. No computability hypothesis is imposed on ttt or SSS. Quantum algorithms and their success probabilities use the published uniform Clifford+T circuit model on binary-coded classical inputs.

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

/-- The Gaussian interface and quantum worst-case reduction in Appendix I.1,
independent of LAR and affine fiber transport. Finite exceptional dimensions are included. -/
theorem fixed_family_gaussian_lwe_worst_case :
    ∃ C k : ℕ, 1 ≤ C ∧ ∀ B : Family, IsQPT B →
      ∀ t : ℕ → ℕ, (∀ lam, 1 ≤ t lam) → PolyBoundedFn t →
        ∀ b : ℕ, ∀ S : Set ℕ, S.Infinite → (∀ lam ∈ S, 1 ≤ lam) →
          (∃ lam₀ : ℕ, ∀ lam ∈ S, lam₀ ≤ lam →
            (lam : ℝ) ^ (-(b : ℝ)) ≤
              advLWE B lam (famPP lam) (famq lam) (famN lam) (famd lam) (t lam)
                (chiG (famq lam) (famd lam) (famσ 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^0 Pseudorandomness from Worst-Case Lattices, https://arxiv.org/html/2611.05136v1, Section 9.9 (p. 58), Appendix I.1 (pp. 132–133), using the cited Peikert full-version Theorem 3.1 and Regev full-version Theorem 3.1, Lemmas 4.1–4.2, 3.11 and 3.14. Finite-dimensional patch makes the source asymptotic guarantee valid at every positive parameter in S.

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