Fixed-family Gaussian LWE search to joint lattice Gaussian sampling
ProvedInfoLossLAR.WorstCase.RegevSearch.search_to_dgsLet be an infinite set of positive security parameters. Suppose one uniform quantum polynomial-time algorithm recovers every secret with probability at least from fresh fixed-family Gaussian LWE tables, using one fixed polynomial number of blocks, at every sufficiently large parameter in . Then there is one uniform quantum polynomial-time sampler and one negligible function such that, for every sufficiently large , satisfies the joint-output lattice Gaussian sampling contract .
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
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.
import Definitions.Def_InfoLossLAR_RegevSearch set_option autoImplicit false open QAlgorithms.Complexity InfoLossLAR.WorstCase open InfoLossLAR.WorstCase.RegevSketch InfoLossLAR.WorstCase.RegevSearch
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