Uniform finite-dimensional patch for GapSVP solvers
ProvedInfoLossLAR.WorstCase.RegevSketch.finite_gap_patchlar-regev-bridgelatticeslearning-with-errorsquantum-computing
Let be a uniform quantum polynomial-time decision algorithm, let be a fixed natural-number cutoff, and let satisfy at positive dimensions. There is a uniform quantum polynomial-time algorithm such that, for every positive ,
Every solver guarantee quantifies over all nonsingular integer bases and positive rational promise thresholds. Thus the finitely many dimensions below still contain infinitely many binary-coded inputs.
This formalization obligation combines exact fixed-rank lattice algorithms with a uniform family that inherits the given solver’s guarantee above the cutoff. It extends an eventual guarantee to all positive dimensions and makes no computability assumption on . It is not a finite lookup table of lattice instances.
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 finite_gap_patch (A : Family) (hA : IsQPT A) (cutoff : ℕ) (gamma : ℕ → ℝ)
(hgamma : ∀ n,1 ≤ n → 1 ≤ gamma n) :
∃ patched : Family,IsQPT patched ∧ ∀ n,1 ≤ n →
(cutoff ≤ n → SolvesGapSVP A (famN n) (gamma n)) →
SolvesGapSVP patched (famN n) (gamma n) := 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. Finite-dimensional completion required by the original fixed-family Gaussian worst-case target (Appendix I.1); uses exact fixed-rank lattice algorithms and a uniform finite dispatcher. This patch is an explicit formalization obligation, not a separately numbered lemma in Regev.