Exact SIVP in dimensions below a fixed cutoff
ProvedInfoLossLAR.WorstCase.RegevSketch.finite_exact_sivpFix an integer cutoff . There is a uniform quantum polynomial-time family such that, on every nonsingular integer basis of dimension , it outputs with probability at least an encoding of independent vectors in whose lengths are at most the last successive minimum:
The basis entries may have arbitrary finite binary lengths. The polynomial running-time bound may depend on the fixed cutoff but must hold uniformly over all such inputs and all dimensions below it. This is an explicit finite-rank algorithm and machine-model bridge obligation for the worst-case reduction; it does not enumerate a finite collection of input bases.
Formalization Note. The output starts with the encoding of the vectors in the ambient coordinates, and the circuit family is uniform over the platform's Clifford+T gate set. Micciancio and Voulgaris supply the exact lattice algorithm motivation, but their stated bit-size regime and the conversion to this uniform circuit model require separate verification.
import Definitions.Def_InfoLossLAR_RegevSketch_DGS set_option autoImplicit false open QAlgorithms.Complexity open InfoLossLAR.WorstCase
namespace InfoLossLAR.WorstCase.RegevSketch
theorem finite_exact_sivp (cutoff : ℕ) :
∃ E : MFamily, IsMQPT E ∧ ∀ n, 1 ≤ n → n < cutoff → SolvesSIVP E (famN n) 1 := by sorry
end InfoLossLAR.WorstCase.RegevSketch