Classical exact SIVP below a fixed dimension cutoff
ProvedInfoLossLAR.WorstCase.RegevSketch.finite_exact_sivp_classicalFix a natural-number cutoff . There exists a deterministic polynomial-time function on binary strings which, for every nonsingular integer basis in dimension , outputs a string beginning with an encoding of independent lattice vectors such that
The running-time polynomial may depend on , but the input basis entries may have arbitrary finite binary length. The function is total on all binary strings; only valid nonsingular basis encodings are required to satisfy the output condition. The statement isolates the classical lattice-algorithm obligation used in the finite-dimensional patch.
Formalization Note. The underlying time predicate uses the platform's multi-stack Turing machine. The output encodes vectors in ambient coordinates. The exact SIVP algorithm and the fixed-dimension input-length adaptation are motivated by Micciancio and Voulgaris; matching their algorithms to this particular machine and encoding is part of this open obligation.
import Definitions.Def_InfoLossLAR_RegevSketch_DGS set_option autoImplicit false open QAlgorithms.Complexity InfoLossLAR.WorstCase
namespace InfoLossLAR.WorstCase.RegevSketch
theorem finite_exact_sivp_classical (cutoff : ℕ) :
∃ f : Str → Str, PolyTimeComputable f ∧
∀ n, 1 ≤ n → n < cutoff → ∀ B : Matrix (Fin n) (Fin n) ℤ, B.det ≠ 0 →
∃ y : Fin n → Fin n → ℤ, encVec (encVec encI) y <+: f (encMat encI B) ∧
(∀ i, intVecE (y i) ∈ lattice B) ∧ LinearIndependent ℝ (fun i => intVecE (y i)) ∧
∀ i, ‖intVecE (y i)‖ ≤ lamN B := by sorry
end InfoLossLAR.WorstCase.RegevSketch