Uniform SIVP from a concrete joint DGS sampler
ProvedInfoLossLAR.WorstCase.RegevSketch.dgs_to_sivplar-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 multi-output quantum polynomial-time algorithm and a cutoff such that, at every positive dimension beyond the cutoff,
Success is required on every nonsingular integer-basis input, with the original platform vector encoding and success probability. The constants are fixed before the sampler and its error function; the algorithm and cutoff may depend on them.
The statement isolates the SIVP branch, including actual scale search and candidate selection. It does not assume that a satisfying DGS sampler exists.
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_sivp :
∃ C k : ℕ,1 ≤ C ∧ ∀ G : MFamily,IsMQPT G →
∀ error : ℕ → ℝ,Negligible error →
∃ A : MFamily,IsMQPT A ∧ ∃ cutoff : ℕ,∀ n ≥ cutoff,1 ≤ n →
DGSAt G n (error n) →
SolvesSIVP 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. Lemmas 3.15–3.17, full-version PDF pp. 28–29; fixed-family substitution and explicit uniform multi-output realization.