Bounded-distance decoding with a Gaussian sample pool
DefinitionInfoLossLAR_RegevSearch_SharedPoolBDDThe decoder receives an integer basis , a positive rational width , a unary precision , one pool of integer coefficient vectors, and a rational query . For a dual lattice point within distance of , the required readout is the signed integer vector . The nearby point and its coordinates specify the success event. The circuit receives only the query and public data together with the sample pool.
The pool has independent draws from the coefficient law for . For each fixed query, average its measurement failure probability over this pool. The basic contract bounds this average by above the public Gaussian smoothing threshold. The coherent-use budget evaluates the same average at precision for a polynomial call bound . It bounds times the square root of that average by a negligible residual plus . Both contracts use the same decoding routine for every promised basis, width and query.
import Definitions.Def_InfoLossLAR_RegevSearch
set_option autoImplicit false
namespace InfoLossLAR.WorstCase.RegevSearch
open QAlgorithms.Complexity InfoLossLAR.WorstCase.RegevSketch RegevLWE.GaussConv
open scoped BigOperators Classical
/-- A decoder receives the public basis, Gaussian width, unary accuracy budget, one
fixed pool of integer coefficient vectors, and the rational query. -/
def poolBDDInput {n m : ℕ} (B : Matrix (Fin n) (Fin n) ℤ) (R : ℚ) (k : ℕ)
(pool : Fin m → Fin n → ℤ) (x : Fin n → ℚ) : Str :=
encPair (encMat encI B) (encPair (encQ R) (encPair (unary k)
(encPair (encVec (encVec encI) pool) (encVec encQ x))))
/-- Failure on one fixed query, averaging the Born probability over independent ideal
Gaussian coefficient vectors in the one shared input pool. -/
noncomputable def poolBDDFailure (C : MFamily) {n : ℕ} (m : ℕ)
(B : Matrix (Fin n) (Fin n) ℤ) (R : ℚ) (k : ℕ) (x : Fin n → ℚ) (z : Fin n → ℤ) : ℝ :=
∑' pool : Fin m → Fin n → ℤ, (∏ j, coefficientMass B (R : ℝ) (pool j)) *
outputProb C (poolBDDInput B R k pool x) (fun out => ¬ encVec encI z <+: out)
/-- For each fixed query in the decoding radius, the decoder recovers the signed
coordinates `z = Bᵀu` of the nearby dual point `u`. The failure probability averages
one ideal Gaussian pool and the quantum measurement on that pool. The pool size is a
public polynomial in the dimension, shared by all queries and all accuracy budgets. -/
def SharedPoolBDD (C : MFamily) (poolSize : Polynomial ℕ) (error : ℕ → ℝ)
(cutoff : ℕ) (S : Set ℕ) : Prop :=
∀ n ∈ S, cutoff ≤ 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 →
poolBDDFailure C (poolSize.eval n) B R k x z ≤ error n + 1 / ((k : ℝ) + 1)
/-- Unary accuracy for each decoder call in a coherent computation with a public
bound on the number of invocations. -/
def poolBDDPrecision (calls budget : ℕ) : ℕ := (16 * (calls+1) * (budget+1))^2
/-- A square-root failure budget for a polynomial number of coherent decoder uses.
The query for each use is fixed before averaging the reference sample pool. -/
def CoherentPoolBDDBudget (C : MFamily) (poolSize : Polynomial ℕ) (cutoff : ℕ)
(S : Set ℕ) : Prop :=
∀ calls : Polynomial ℕ, ∃ residual : ℕ → ℝ, Negligible residual ∧
∀ n ∈ S, cutoff ≤ n → ∀ B : Matrix (Fin n) (Fin n) ℤ, B.det ≠ 0 →
∀ R : ℚ, 0 < R →
Real.sqrt 2 * (famq n : ℝ) * smoothingParam (inputModule B) (smoothingError n) < (R : ℝ) →
∀ (budget : ℕ) (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 →
4 * ((calls.eval n : ℕ) : ℝ) * Real.sqrt (poolBDDFailure C (poolSize.eval n) B R
(poolBDDPrecision (calls.eval n) budget) x z) ≤
residual n + 1 / (4 * ((budget : ℝ)+1))
end InfoLossLAR.WorstCase.RegevSearch