One lattice Gaussian coefficient vector from fixed-family LWE search
ProvedInfoLossLAR.WorstCase.RegevSearch.search_to_single_coefficient_gaussianLet be an infinite set of positive dimensions. At each sufficiently large , suppose one uniform quantum polynomial-time algorithm recovers each fixed secret with probability at least from a fresh table of the specified fixed-family discrete Gaussian LWE distribution. One polynomial bounds the number of table blocks.
There is a uniform quantum polynomial-time sampler and a negligible function . For every sufficiently large , every nonsingular integer basis , every positive rational width at least the platform DGS threshold, and every unary precision parameter , the measured output of starts with a valid encoding of a single vector of integer coefficients. If is the probability of the prefix encoding and is the normalized Gaussian coefficient mass for the original basis, then
The sampler uses the DGS input format with count one and emits the inner coefficient-vector encoding. The same family and intrinsic error apply to every basis, width and precision in a given dimension. This is the one-sample search-to-DGS construction needed before independent repetitions can supply a whole pool.
import Definitions.Def_InfoLossLAR_RegevSearch set_option autoImplicit false open QAlgorithms.Complexity InfoLossLAR.WorstCase InfoLossLAR.WorstCase.RegevSketch open scoped BigOperators Classical
namespace InfoLossLAR.WorstCase.RegevSearch
theorem search_to_single_coefficient_gaussian
(S : Set ℕ) (hS : S.Infinite) (hpos : ∀ n ∈ S, 1 ≤ n)
(A : MFamily) (hA : IsMQPT A) (samples : Polynomial ℕ) (cutoff : ℕ)
(hsearch : SearchOn A samples cutoff S) :
∃ H : MFamily, IsMQPT H ∧ ∃ error : ℕ → ℝ, Negligible error ∧
∃ threshold : ℕ, ∀ n ∈ S, threshold ≤ n →
∀ B : Matrix (Fin n) (Fin n) ℤ, B.det ≠ 0 →
∀ r : ℚ, 0 < r → dgsThreshold B ≤ (r : ℝ) →
∀ precision : ℕ,
let draw (z : Fin n → ℤ) := outputProb H (dgsInput B r 1 precision)
(fun out => encVec encI z <+: out)
HasSum draw 1 ∧
(∑' z, |draw z - coefficientMass B r z|) ≤
error n + 1 / ((precision : ℝ) + 1) := by
sorry
end InfoLossLAR.WorstCase.RegevSearch