Lemma 8 — structure of the ANF coefficients of MOD12
OpenGoldreichAffine.Exponential.Supplement.mod12_anf_structureboolean-functionscryptographyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let with if and otherwise; these are the ANF coefficients of . For every and every ,
Moreover, for every :
- the sequence contains no six consecutive zeros, i.e. for every some with has ;
- at least one of is nonzero.
The degree lower bound of Theorem 4 is read off these clauses.
Differences from the source:
- encoding: (λ_j(w))_{j≥4} contains no six consecutive zeros → ∀ w, ∀ j ≥ 4, ∃ i, j ≤ i ≤ j+5 ∧ λ_i(w) ≠ 0; reason: same statement, quantified explicitly
Preamble
import Definitions.Def_GoldreichAffine_Exponential_Supplement_Modular open MatousekLP.Codes (Word weight) set_option autoImplicit false
Formal statement
namespace GoldreichAffine.Exponential.Supplement
/-- Lemma 8, printed p.31 / PDF p.32: all four clauses, for every w ≥ 0. -/
theorem mod12_anf_structure :
(∀ w j : ℕ, 4 ≤ j →
binomialTransform mod12Sequence (j + 12) w = binomialTransform mod12Sequence j w ∧
binomialTransform mod12Sequence j (w + 4) = binomialTransform mod12Sequence (j + 8) w) ∧
(∀ w j : ℕ, 4 ≤ j → ∃ i : ℕ, j ≤ i ∧ i ≤ j + 5 ∧ binomialTransform mod12Sequence i w ≠ 0) ∧
(∀ w : ℕ, binomialTransform mod12Sequence 4 w ≠ 0 ∨
binomialTransform mod12Sequence 5 w ≠ 0 ∨ binomialTransform mod12Sequence 6 w ≠ 0) := 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. 31 (PDF p. 32), Lemma 8; proof pp. 31–32 (PDF pp. 32–33)