Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Fixed-family Gaussian LWE search to joint lattice Gaussian sampling

Proved
InfoLossLAR.WorstCase.RegevSearch.search_to_dgs

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

lar-regev-bridgelatticeslearning-with-errorsquantum-computing

Let SSS be an infinite set of positive security parameters. Suppose one uniform quantum polynomial-time algorithm recovers every secret with probability at least 3/43/43/4 from fresh fixed-family Gaussian LWE tables, using one fixed polynomial number of blocks, at every sufficiently large parameter in SSS. Then there is one uniform quantum polynomial-time sampler GGG and one negligible function ε\varepsilonε such that, for every sufficiently large n∈Sn\in Sn∈S, GGG satisfies the joint-output lattice Gaussian sampling contract DGSAt⁡(G,n,ε(n))\operatorname{DGSAt}(G,n,\varepsilon(n))DGSAt(G,n,ε(n)).

For every nonsingular integer basis and every positive rational width at least the contract threshold, this contract bounds the discrepancy of every event on the whole decoded coefficient pool by

count⋅ε(n)+1budget+1.\text{count}\cdot\varepsilon(n)+\frac{1}{\text{budget}+1}.count⋅ε(n)+budget+11​.

The input explicitly includes the output count and numerical budget in unary. The obligation includes arbitrary basis encodings, the joint output law, and a negligible term independent of the basis and requested budget. It is not a claim that the searcher works on smaller-noise inputs, that repeated calls using a shared pool are independent, or that the sampler is already constructed.

Formalization Note. This is a fixed-family, discrete-noise and uniform-circuit formulation inspired by Regev's continuous-noise reduction. The noise conversion, success amplification, coherent BDD use, numerical errors, iteration, and full joint-law strengthening remain part of this open theorem rather than being assumed as already proved by the source.

Preamble
import Definitions.Def_InfoLossLAR_RegevSearch

set_option autoImplicit false
open QAlgorithms.Complexity InfoLossLAR.WorstCase
open InfoLossLAR.WorstCase.RegevSketch InfoLossLAR.WorstCase.RegevSearch
Formal statement
namespace InfoLossLAR.WorstCase.RegevSearch
theorem search_to_dgs : ∀ (S : Set ℕ), S.Infinite → (∀ n ∈ S, 1 ≤ n) →
      ∀ (A : MFamily), IsMQPT A → ∀ (samples : Polynomial ℕ) (cutoff : ℕ),
        SearchOn A samples cutoff S →
        ∃ G : MFamily, IsMQPT G ∧ ∃ error : ℕ → ℝ, InfoLossLAR.WorstCase.Negligible error ∧
          ∃ threshold : ℕ, ∀ n ∈ S, threshold ≤ n → DGSAt G n (error n) := by sorry
end InfoLossLAR.WorstCase.RegevSearch
Source
Oded Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, https://cims.nyu.edu/~regev/papers/qcrypto.pdf, Theorem 3.1 and Lemmas 3.2–3.7, 3.11 and 3.14, pp. 18–28; Chen Qian, arXiv:2611.05136, Appendix I.1, pp. 132–133. The precise discrete Gaussian, fixed-family encodings, uniform circuit, numeric and joint-output conditions are explicit formalization obligations and are not a verbatim claim of either source.

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