Fixed-family Gaussian LWE to quantum worst-case GapSVP and SIVP
ProvedInfoLossLAR.WorstCase.fixed_family_gaussian_lwe_worst_caseFor the fixed public family of Section 9.9, there exist constants , with , satisfying the following statement. Let be a uniform QPT Gaussian block-LWE distinguisher, let be a positive polynomially bounded block-count function, let , and let be an infinite set of positive security parameters. Suppose that, for all sufficiently large ,
where the block error distribution is and the distinguisher receives the fixed family's public parameters.
There exist uniform quantum polynomial-time algorithms solving worst-case and , respectively, in dimension , for every , where
The algorithms satisfy the published worst-case success requirements on every nonsingular integer-basis instance. The constants are fixed before .
This is the Gaussian-LWE interface to the quantum worst-case lattice reduction, independent of LAR and affine fiber transport.
Formalization Note. The hypothesis only requires advantage eventually on , whereas the conclusion includes all positive dimensions in . Finitely many exceptional dimensions are included using exact fixed-dimensional lattice algorithms. No computability hypothesis is imposed on or . Quantum algorithms and their success probabilities use the published uniform Clifford+T circuit model on binary-coded classical inputs.
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_QPT import Definitions.Def_InfoLossLAR_WorstCase_Laws import Definitions.Def_InfoLossLAR_WorstCase_Family import Definitions.Def_InfoLossLAR_WorstCase_LatticeProblems set_option autoImplicit false open QAlgorithms.Complexity
namespace InfoLossLAR.WorstCase
/-- The Gaussian interface and quantum worst-case reduction in Appendix I.1,
independent of LAR and affine fiber transport. Finite exceptional dimensions are included. -/
theorem fixed_family_gaussian_lwe_worst_case :
∃ C k : ℕ, 1 ≤ C ∧ ∀ B : Family, IsQPT B →
∀ t : ℕ → ℕ, (∀ lam, 1 ≤ t lam) → PolyBoundedFn t →
∀ b : ℕ, ∀ S : Set ℕ, S.Infinite → (∀ lam ∈ S, 1 ≤ lam) →
(∃ lam₀ : ℕ, ∀ lam ∈ S, lam₀ ≤ lam →
(lam : ℝ) ^ (-(b : ℝ)) ≤
advLWE B lam (famPP lam) (famq lam) (famN lam) (famd lam) (t lam)
(chiG (famq lam) (famd lam) (famσ lam))) →
(∃ A : Family, IsQPT A ∧ ∀ lam ∈ S,
SolvesGapSVP A (famN lam)
((C : ℝ) * (famq lam : ℝ) * Real.logb 2 ((lam : ℝ) + 2) ^ k)) ∧
(∃ A : MFamily, IsMQPT A ∧ ∀ lam ∈ S,
SolvesSIVP A (famN lam)
((C : ℝ) * (famq lam : ℝ) * Real.logb 2 ((lam : ℝ) + 2) ^ k)) := by sorry
end InfoLossLAR.WorstCase