Gaussian decision advantage yields a uniform joint DGS sampler
ProvedInfoLossLAR.WorstCase.RegevSketch.gaussian_decision_to_dgsLet be a uniform quantum polynomial-time distinguisher, a positive polynomially bounded sample-count function, , and an infinite set of positive parameters. Suppose the advantage of against the fixed public family's Gaussian block-LWE distribution is at least for all sufficiently large .
There are one uniform multi-output quantum polynomial-time family , one negligible function , and a cutoff such that
The concrete DGS predicate concerns arbitrary nonsingular original integer bases, rational widths at or above the fixed smoothing threshold, and complete coefficient pools. The same sampler handles all unary pool sizes and unary numerical-error budgets, with total eventwise error .
This is the open algorithmic core of the reduction. Its source route includes decision-to-search, verification and the noise grid, modular closest-vector recovery, BDD construction, wide-Gaussian initialization, pure-state preparation, the BDD-to-DGS quantum step, and width iteration. The statement does not assume any of these algorithms as an oracle. Neither nor is required to be computable.
import Definitions.Def_InfoLossLAR_RegevSketch_DGS set_option autoImplicit false set_option maxHeartbeats 200000 open QAlgorithms.Complexity open scoped BigOperators Classical
namespace InfoLossLAR.WorstCase.RegevSketch
theorem gaussian_decision_to_dgs :
∀ D : Family,IsQPT D → ∀ t : ℕ → ℕ,(∀ n,1 ≤ t n) → PolyBoundedFn t →
∀ b : ℕ,∀ S : Set ℕ,S.Infinite → (∀ n ∈ S,1 ≤ n) →
(∃ n₀ : ℕ,∀ n ∈ S,n₀ ≤ n → (n : ℝ)^(-(b : ℝ)) ≤
advLWE D n (famPP n) (famq n) (famN n) (famd n) (t n)
(chiG (famq n) (famd n) (famσ n))) →
∃ G : MFamily,IsMQPT G ∧ ∃ error : ℕ → ℝ,Negligible error ∧
∃ cutoff : ℕ,∀ n ∈ S,cutoff ≤ n → DGSAt G n (error n) := by sorry
end InfoLossLAR.WorstCase.RegevSketch