Uniform finite-dimensional patch for SIVP solvers
ProvedInfoLossLAR.WorstCase.RegevSketch.finite_sivp_patchlar-regev-bridgelatticeslearning-with-errorsquantum-computing
Let be a uniform multi-output quantum polynomial-time algorithm, let be a fixed natural-number cutoff, and let satisfy at positive dimensions. There is a uniform multi-output quantum polynomial-time algorithm such that, for every positive ,
The guarantee applies to every nonsingular integer basis and preserves the platform's original-vector output encoding and success probability. No computability assumption is imposed on .
This is the multi-output finite-dimensional completion: exact fixed-rank algorithms handle all input bases below the fixed cutoff, while the resulting uniform family inherits the given solver’s guarantee above the cutoff. It does not replace arbitrary bases by a finite table of answers.
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_sivp_patch (A : MFamily) (hA : IsMQPT A) (cutoff : ℕ) (gamma : ℕ → ℝ)
(hgamma : ∀ n,1 ≤ n → 1 ≤ gamma n) :
∃ patched : MFamily,IsMQPT patched ∧ ∀ n,1 ≤ n →
(cutoff ≤ n → SolvesSIVP A (famN n) (gamma n)) →
SolvesSIVP 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); exact fixed-rank lattice algorithms and a uniform finite dispatcher. This is an explicit formalization obligation rather than a separately numbered Regev lemma.