A dimension-bounded Gaussian width schedule for the input lattice
ProvedInfoLossLAR.WorstCase.RegevSearch.reduced_basis_admissible_width_schedulediscrete-gaussianlar-regev-bridgelattices
Let , let be a nonsingular integer basis in dimension , and let the positive rational satisfy the Gaussian sampling threshold for . There exists another integer basis of the same lattice such that the rational initial width
reaches a valid terminal width after at most halvings. Every source width up to and including the terminal stage exceeds . At the terminal stage , the decoding radius is at least .
Preamble
import Definitions.Def_InfoLossLAR_RegevSketch_DGS set_option autoImplicit false open scoped BigOperators open RegevLWE.GaussConv open InfoLossLAR.WorstCase InfoLossLAR.WorstCase.RegevSketch
Formal statement
namespace InfoLossLAR.WorstCase.RegevSearch
theorem reduced_basis_admissible_width_schedule {n : ℕ} (hn : 2 ≤ n)
(B : Matrix (Fin n) (Fin n) ℤ) (hB : B.det ≠ 0)
(r : ℚ) (hr : 0 < r) (hp : dgsThreshold B ≤ (r : ℝ)) :
∃ D : Matrix (Fin n) (Fin n) ℤ, D.det ≠ 0 ∧ inputModule D = inputModule B ∧
∃ W : ℚ, W = max (((n+1 : ℕ) : ℚ) * (1 + ∑ i, ∑ j, |(D i j : ℚ)|)) (r * (famσ n : ℚ)) ∧
∃ h : ℕ, h ≤ 5*n+2 ∧
(∀ j ≤ h, Real.sqrt 2 * (famq n : ℝ) * smoothingParam (inputModule B) (smoothingError n) <
(W : ℝ) / 2^j) ∧
Real.sqrt n / (Real.sqrt 2 * (r : ℝ)) ≤ (famσ n : ℝ)/(2*((W : ℝ)/2^h)) := by
sorry
end InfoLossLAR.WorstCase.RegevSearchSource
Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, Theorem 3.1 and Lemma 3.3, https://cims.nyu.edu/~regev/papers/qcrypto.pdf. The reduced-basis initialization floor and the bound at arbitrary promised rational width are explicit specializations for https://prove2.me/theorems/9fdfd0c1-342f-4e71-9410-562b6727463a.