Lemma 7 — binomial transform identity
ProvedGoldreichAffine.Exponential.Supplement.binomial_transform_identityboolean-functionscryptographyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a binary sequence over let in . For every modular function (, ), whose coefficients are with , and for all integers ,
The identity also holds for the binomial transform of any binary sequence .
The identity is the tool behind the periodicity of the ANF coefficients of MOD12 (Lemma 8), and hence behind the degree bound of Theorem 4.
Differences from the source:
- encoding: coefficients over F₂ of MOD^{t,S0}_b, and of an arbitrary binary sequence → binomialTransform over ZMod 2 of modSequence t S0 (first conjunct) and of any a : ℕ → ZMod 2 (second conjunct); reason: ZMod 2 is F₂; λ_j(w) does not depend on b, so the MOD clause needs no b
Preamble
import Definitions.Def_GoldreichAffine_Exponential_Supplement_Modular open MatousekLP.Codes (Word weight) set_option autoImplicit false
Formal statement
namespace GoldreichAffine.Exponential.Supplement
/-- Lemma 7, printed p.30 / PDF p.31: lambda_{j+2^k}(w) = lambda_j(w) + lambda_j(w+2^k) over F₂,
for the coefficients of every MOD^{t,S0} and for the binomial transform of any binary sequence. -/
theorem binomial_transform_identity :
(∀ (t : ℕ) (S0 : Finset ℕ), 2 ≤ t → S0 ⊆ Finset.range t → ∀ j k w : ℕ,
binomialTransform (modSequence t S0) (j + 2 ^ k) w =
binomialTransform (modSequence t S0) j w +
binomialTransform (modSequence t S0) j (w + 2 ^ k)) ∧
(∀ (a : ℕ → ZMod 2) (j k w : ℕ),
binomialTransform a (j + 2 ^ k) w =
binomialTransform a j w + binomialTransform a j (w + 2 ^ k)) := 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, p. 30 (PDF p. 31), Lemma 7; proof pp. 30–31 (PDF pp. 31–32)