Concrete joint-output lattice Gaussian sampling contract
DefinitionInfoLossLAR_RegevSketch_DGSFor an integer basis matrix of dimension , let be its column lattice. Set
Here and are the fixed public-family modulus and Gaussian width, and is the published smoothing parameter. The binary size in is the usual natural-number bit length.
The coefficient law at positive width assigns to mass proportional to . The input encoding specifies , a positive rational width , a unary sample count , and a unary inverse numerical-error budget . A successful output begins with the canonical encoding of the complete pool of original-basis coefficient vectors.
The predicate states that, for every nonsingular , every and every event on the complete pool, the difference between the actual output-event probability of the published multi-output circuit family and the independent Gaussian product probability is at most
This package defines the sampling contract and encodings only. It makes no claim that a sampler, BDD decoder, or lattice reduction exists. The constant slack and explicit bit encodings specialize the source's DGS interface to the fixed Gaussian-LWE family.
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
import Definitions.Def_RegevLWE_GaussConv_Lattice
set_option autoImplicit false
open QAlgorithms.Complexity
open scoped BigOperators Classical
namespace InfoLossLAR.WorstCase.RegevSketch
noncomputable section
/-- The actual integer input lattice, as a Z-submodule for smoothing. -/
def inputModule {n : ℕ} (B : Matrix (Fin n) (Fin n) ℤ) : Submodule ℤ (EuclideanSpace ℝ (Fin n)) :=
Submodule.span ℤ (Set.range (fun i : Fin n => latVec B (Pi.single i 1)))
/-- One fixed negligible smoothing schedule; independent of the adversary. -/
def smoothingError (n : ℕ) : ℝ := 1/(2 : ℝ)^((Nat.size (n+2))^2)
/-- Regev's DGS threshold, with an absolute slack constant and alpha=sigma/q.
The square-root is an analysis parameter; samplers receive rational widths. -/
def dgsThreshold {n : ℕ} (B : Matrix (Fin n) (Fin n) ℤ) : ℝ :=
(16*(famq n : ℝ)*Real.sqrt n/(famσ n : ℝ))*
RegevLWE.GaussConv.smoothingParam (inputModule B) (smoothingError n)
/-- True normalized coefficient law of D_(L(B),r), using the original B. -/
def coefficientMass {n : ℕ} (B : Matrix (Fin n) (Fin n) ℤ) (r : ℝ) (z : Fin n → ℤ) : ℝ :=
rhoInt r (B.mulVec z)/(∑' y : Fin n → ℤ,rhoInt r (B.mulVec y))
/-- Unary count and inverse-error budget keep the requested output and
approximation work inside the native input size. -/
def dgsInput {n : ℕ} (B : Matrix (Fin n) (Fin n) ℤ) (r : ℚ) (count budget : ℕ) : Str :=
encPair (encMat encI B) (encPair (encQ r) (encPair (unary count) (unary budget)))
/-- The actual measured output must encode the whole original-basis
coefficient pool before any event on the pool is tested. -/
def decodedPoolEvent {n count : ℕ} (event : (Fin count → Fin n → ℤ) → Prop) (out : Str) : Prop :=
∃ pool : Fin count → Fin n → ℤ,encVec (encVec encI) pool <+: out ∧ event pool
/-- Complete joint DGS correctness for one actual multi-output family.
This is a problem contract, not an existence assumption: all missing
algorithmic existence claims are explicit open child theorems. -/
def DGSAt (A : MFamily) (n : ℕ) (error : ℝ) : Prop :=
∀ B : Matrix (Fin n) (Fin n) ℤ,B.det ≠ 0 →
∀ r : ℚ,0 < r → dgsThreshold B ≤ (r : ℝ) →
∀ count budget : ℕ,∀ event : (Fin count → Fin n → ℤ) → Prop,
|outputProb A (dgsInput B r count budget) (decodedPoolEvent event)-
∑' pool : Fin count → Fin n → ℤ,
(∏ i,coefficientMass B r (pool i))*(if event pool then 1 else 0)| ≤
(count : ℝ)*error+1/((budget : ℝ)+1)
end
end InfoLossLAR.WorstCase.RegevSketch