Lemma 5 — Fourier bound for modular bit-fixing affine advantage
OpenGoldreichAffine.Exponential.Supplement.modular_fourier_boundboolean-functionscryptographyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and with and
Let be the signed weight profile and its Fourier coefficients. For and let be any residual of obtained by fixing inputs, and let . For every affine function with and , the agreement probability satisfies
Consequently, for every ,
The lemma gives the sufficiency direction of Theorem 3, and (22) is the input to the explicit MOD12 bound of Theorem 6.
Differences from the source:
- encoding: M′ a residual of M_b obtained by fixing r inputs, 0 ≤ r < b, b ≥ 1 → M′ : Predicate (b − r) with IsResidual (published), r < b; reason: the published residual relation fixes exactly b − (b − r) = r inputs; b ≥ 1 follows from r < b
- encoding: |S0 ∩ 2Z|, |S0 ∩ (2Z+1)|, S0 ⊆ {0,…,t−1} → (S0.filter Even).card, (S0.filter Odd).card, S0 ⊆ Finset.range t; reason: same sets
- encoding: (23) for every 1 ≤ b′ ≤ b with b ≥ 1 → ∀ b b′, 1 ≤ b′ → b′ ≤ b; reason: b ≥ 1 follows from 1 ≤ b′ ≤ b
Preamble
import Definitions.Def_GoldreichAffine_Exponential_Supplement_Modular open scoped BigOperators open MatousekLP.Codes (Word weight) set_option autoImplicit false
Formal statement
namespace GoldreichAffine.Exponential.Supplement
/-- Lemma 5, printed pp.25–26 / PDF pp.26–27: both (22) and (23). -/
theorem modular_fourier_bound (t : ℕ) (S0 : Finset ℕ) (ht : 2 ≤ t)
(hS0 : S0 ⊆ Finset.range t) (h4 : 4 ∣ t)
(heven : (S0.filter Even).card = t / 4) (hodd : (S0.filter Odd).card = t / 4) :
(∀ b r : ℕ, r < b → ∀ M' : Predicate (b - r), IsResidual (modPredicate t S0 b) M' →
∀ (c : Bool) (A : Finset (Fin (b - r))),
|uniformAgreement M' (affine c A) - 1 / 2| ≤
1 / 2 * ∑ ν ∈ (Finset.range t).filter (fun ν => ν ≠ 0 ∧ ν ≠ t / 2),
‖fourierCoeff t S0 ν‖ * |Real.sin (Real.pi * (ν : ℝ) / (t : ℝ))| ^ A.card *
|Real.cos (Real.pi * (ν : ℝ) / (t : ℝ))| ^ (b - r - A.card)) ∧
(∀ b b' : ℕ, 1 ≤ b' → b' ≤ b →
advantage (modPredicate t S0 b) b' ≤
min (1 / 2) (Real.sqrt ((t : ℝ) - 2) / 2 * Real.cos (Real.pi / (t : ℝ)) ^ b')) := by sorry
end GoldreichAffine.Exponential.Supplement
Source
Ximing Fu, Mo Li, Shihan Lyu, Affine Advantage in Guess-type Attacks on Goldreich’s PRGs: Generalization, Characterization and Countermeasures, STOC 2027 submission #579 (October 2026), PDF SHA-256 c6e5f1bfbc08adde62b9863b4417adb47a894635ef9e887e40be2e7fcd8c0594, pp. 25–26 (PDF pp. 26–27), Lemma 5, Eqs. (21)–(23)