Uniform GapSVP from a concrete joint DGS sampler
ProvedInfoLossLAR.WorstCase.RegevSketch.dgs_to_gapsvplar-regev-bridgelatticeslearning-with-errorsquantum-computing
There are absolute natural numbers , with , with the following property. For every uniform multi-output quantum polynomial-time family and every negligible function , there are a uniform quantum polynomial-time decision algorithm and a cutoff such that, at every positive dimension beyond the cutoff,
The guarantee is the published worst-case promise decision requirement on every nonsingular integer basis and every positive rational threshold. The constants precede the sampler and error function.
This branch includes the external promise-problem reduction and verifier used by the source's GapSVP argument. A collection of short lattice vectors does not itself discharge this decision-algorithm obligation.
Preamble
import Definitions.Def_InfoLossLAR_RegevSketch_DGS set_option autoImplicit false set_option maxHeartbeats 200000 open QAlgorithms.Complexity open scoped BigOperators Classical
Formal statement
namespace InfoLossLAR.WorstCase.RegevSketch
theorem dgs_to_gapsvp :
∃ C k : ℕ,1 ≤ C ∧ ∀ G : MFamily,IsMQPT G →
∀ error : ℕ → ℝ,Negligible error →
∃ A : Family,IsQPT A ∧ ∃ cutoff : ℕ,∀ n ≥ cutoff,1 ≤ n →
DGSAt G n (error n) →
SolvesGapSVP A (famN n) ((C : ℝ)*(famq n : ℝ)*Real.logb 2 ((n : ℝ)+2)^k) := by sorry
end InfoLossLAR.WorstCase.RegevSketchSource
Oded Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, full version dated May 2, 2009, https://cims.nyu.edu/~regev/papers/qcrypto.pdf. Lemma 3.20 and its preceding reduction from GapSVP to the promise GapCVP variant, full-version PDF p. 30; fixed-family substitution and explicit uniform decision algorithm.