Fixed-family LAR to Gaussian LWE: inverse-polynomial advantage transfer
ProvedInfoLossLAR.WorstCase.fixed_family_gaussian_advantage_transferConsider the fixed public family of Section 9.9, with secret dimension , Gaussian width , and the modulus, block dimension and label function defined there. Suppose this family admits fixed-order Gaussian affine fiber transports in the sense of Definition 5.3.
For every uniform QPT LAR distinguisher , every positive polynomially bounded sample-count function , and every , there exist a uniform QPT Gaussian-LWE distinguisher , an exponent , and a threshold such that, for every positive ,
Gaussian LWE uses the same public parameters and blocks of dimension , with error distribution . The reduction runs once on a classically prepared input.
This isolates the transfer of inverse-polynomial distinguishing advantage from LAR to Gaussian LWE. The reduction and its exponent are independent of any later restriction to an infinite set of security parameters.
Formalization Note. This is the fixed-family consequence of Corollary 5.5 after polynomial-loss absorption, as used in Appendix I.1. Polynomial boundedness of does not assert its computability. The statement uses the fixed family's published binary encoding of public parameters.
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
/-- Corollary 5.5 and polynomial-loss absorption for the fixed family of Section 9.9.
The distinguisher and advantage exponent are chosen before any success subsequence. -/
theorem fixed_family_gaussian_advantage_transfer
(hAFT : AdmitsFixedOrderGaussianAFT famInput famq famd (fun _ => 1)
(fun lam => (famσ lam : ℝ)) famLabel)
(D : Family) (hD : IsQPT D)
(t : ℕ → ℕ) (ht : ∀ lam, 1 ≤ t lam) (htp : PolyBoundedFn t) (c : ℕ) :
∃ B : Family, IsQPT B ∧ CallsOnce B D ∧ ∃ b lam₀ : ℕ,
∀ lam : ℕ, lam₀ ≤ lam → 1 ≤ lam →
(lam : ℝ) ^ (-(c : ℝ)) ≤ famAdvLAR D lam (t lam) →
(lam : ℝ) ^ (-(b : ℝ)) ≤
advLWE B lam (famPP lam) (famq lam) (famN lam) (famd lam) (t lam)
(chiG (famq lam) (famd lam) (famσ lam)) := by sorry
end InfoLossLAR.WorstCase