A polynomial-size list of dual decoding candidates from fixed-family search
ProvedInfoLossLAR.WorstCase.RegevSearch.search_to_dual_candidate_listsSuppose a uniform quantum algorithm solves search on fresh tables from the prescribed LWE family on all sufficiently large dimensions in an infinite set . Assume the simultaneous variance-grid estimate for all stages of the modular recursion. There is a uniform quantum family and a polynomial such that the following holds for all sufficiently large . Given a nonsingular integer basis , rational , a fixed rational query and unary accuracy , the family receives independent Gaussian coefficient samples at width . If and , the measured word begins with an encoding of a finite list containing except with probability at most , for a negligible . The probability averages the pool and the circuit measurement. Additional candidates may occur in any order.
import Definitions.Def_InfoLossLAR_RegevSearch_SharedPoolBDD set_option autoImplicit false open QAlgorithms.Complexity InfoLossLAR.WorstCase InfoLossLAR.WorstCase.RegevSketch open RegevLWE.GaussConv open scoped BigOperators Classical
namespace InfoLossLAR.WorstCase.RegevSearch
theorem search_to_dual_candidate_lists
(hgrid : ∀ (s q M : ℕ), 2 ≤ s → 2 ≤ q → 0 < M → ∀ E : ℝ, 0 ≤ E → E ≤ (s : ℝ)^2 / 2 →
∃ i : Fin (M + 1), ∀ j : ℕ,
let den : ℚ := (q : ℚ)^(2*j)
let v : ℚ := (s : ℚ)^2 - ((s : ℚ)^2/2) * (i.val : ℚ) / M / den
let total := E / (den : ℝ) + (v : ℝ)
let mass := fun (width : ℝ) (z : ℤ) => AFT.GaussianSource.weight width z /
AFT.GaussianSource.realNormalizer width
(s : ℚ)^2/2 ≤ v ∧ v ≤ (s : ℚ)^2 ∧
0 ≤ (s : ℝ)^2 - total ∧
(s : ℝ)^2 - total ≤ (s : ℝ)^2 / (2 * M * (den : ℝ)) ∧
(∑' z : ℤ, |mass (Real.sqrt total) z - mass (s : ℝ) z|)/2 ≤
1 / ((M : ℝ) * (den : ℝ)))
(S : Set ℕ) (hS : S.Infinite) (hpos : ∀ n ∈ S, 1 ≤ n)
(A : MFamily) (hA : IsMQPT A) (samples : Polynomial ℕ) (cutoff : ℕ)
(hsearch : SearchOn A samples cutoff S) :
∃ T : MFamily, IsMQPT T ∧ ∃ P : Polynomial ℕ, ∃ e : ℕ → ℝ, Negligible e ∧
∃ N : ℕ, ∀ n ∈ S, N ≤ n → ∀ B : Matrix (Fin n) (Fin n) ℤ, B.det ≠ 0 →
∀ R : ℚ, 0 < R →
Real.sqrt 2 * (famq n : ℝ) * smoothingParam (inputModule B) (smoothingError n) < (R : ℝ) →
∀ (k : ℕ) (x u : Fin n → ℚ) (z : Fin n → ℤ),
(∀ j, ∑ i, (B i j : ℚ) * u i = (z j : ℚ)) →
(R : ℝ)^2 * (∑ i, (((x i-u i : ℚ) : ℝ))^2) < (famσ n : ℝ)^2 / 4 →
(∑' pool : Fin (P.eval n) → Fin n → ℤ,
(∏ j, coefficientMass B (R : ℝ) (pool j)) *
outputProb T (poolBDDInput B R k pool x) (fun out => ¬ ∃ vs : List (List ℚ × List ℤ),
encL (fun p : List ℚ × List ℤ => encPair (encL encQ p.1) (encL encI p.2)) vs <+: out ∧
(List.ofFn u,List.ofFn z) ∈ vs)) ≤ e n + 1 / ((k : ℝ)+1) := by
sorry
end InfoLossLAR.WorstCase.RegevSearch