Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Symmetric predicates, algebraic degree and algebraic immunity (Definition 3)

Definition
GoldreichAffine_Exponential_Supplement_Algebraic

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

boolean-functionscryptographyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

A predicate P:{0,1}d→{0,1}P:\{0,1\}^d\to\{0,1\}P:{0,1}d→{0,1} is symmetric if its value depends only on the Hamming weight of its input.

Every PPP has a unique algebraic normal form P(x)=⨁A⊆[d]λA∏j∈AxjP(x)=\bigoplus_{A\subseteq[d]}\lambda_A\prod_{j\in A}x_jP(x)=⨁A⊆[d]​λA​∏j∈A​xj​ over F2\mathbb F_2F2​. Its algebraic degree is

deg⁡(P)=max⁡({0}∪{∣A∣:λA=1}).\deg(P)=\max\big(\{0\}\cup\{|A|:\lambda_A=1\}\big).deg(P)=max({0}∪{∣A∣:λA​=1}).

A Boolean function f≢0f\not\equiv0f≡0 on ddd inputs annihilates PPP if fP≡0fP\equiv0fP≡0 (pointwise product). The algebraic immunity of PPP is

AI(P)=min⁡{deg⁡(f):f≢0, fP≡0 or f(P⊕1)≡0}.\mathrm{AI}(P)=\min\{\deg(f): f\not\equiv0,\ fP\equiv0\ \text{or}\ f(P\oplus1)\equiv0\}.AI(P)=min{deg(f):f≡0, fP≡0 or f(P⊕1)≡0}.

The set of candidate degrees is never empty: 1⊕P1\oplus P1⊕P annihilates PPP unless P≡1P\equiv1P≡1, and then PPP annihilates P⊕1P\oplus1P⊕1. These notions state Theorems 4 and 5 and Lemmas 9 and 10.

Formalization Note The ANF coefficients are the published Möbius coefficients λA=⨁B⊆AP(1B)\lambda_A=\bigoplus_{B\subseteq A}P(\mathbf 1_B)λA​=⨁B⊆A​P(1B​) (ParityCubes.anfCoeff), which are the unique ANF coefficients. The minimum is a natural-number infimum; a sorry-free lemma in the file proves the candidate set nonempty, so the empty-set default of the infimum never applies.

Definition code
import Definitions.Def_GoldreichAffine_Exponential_BooleanCore
import Definitions.Def_ParityCubes_anfCoeff
open scoped BigOperators
open MatousekLP.Codes (Word weight)
set_option autoImplicit false

namespace GoldreichAffine.Exponential.Supplement

/-- A predicate is symmetric if its value depends only on the Hamming weight (printed p.3 / PDF p.4). -/
def IsSymmetric {d : ℕ} (P : Predicate d) : Prop :=
  ∀ x y : Word d, weight x = weight y → P x = P y

/-- Definition 3 (printed p.5 / PDF p.6): deg(P) = max({0} ∪ {|A| : λ_A = 1}).
    The ANF coefficients λ_A are the published Möbius coefficients `ParityCubes.anfCoeff`;
    the sup of the empty family is 0, which is the {0} in the definition. -/
def algebraicDegree {d : ℕ} (P : Predicate d) : ℕ :=
  ((Finset.univ : Finset (Finset (Fin d))).filter
    (fun A => ParityCubes.anfCoeff P A = true)).sup Finset.card

/-- f ≢ 0 and f annihilates P (f·P ≡ 0) or P ⊕ 1 (f·(P ⊕ 1) ≡ 0). -/
def IsAnnihilatorOf {d : ℕ} (P f : Predicate d) : Prop :=
  f ≠ (fun _ => false) ∧
    ((∀ x, (f x && P x) = false) ∨ (∀ x, (f x && !P x) = false))

/-- Degrees of all annihilators of P or of P ⊕ 1. -/
def annihilatorDegrees {d : ℕ} (P : Predicate d) : Set ℕ :=
  {k | ∃ f : Predicate d, IsAnnihilatorOf P f ∧ algebraicDegree f = k}

/-- The candidate set is never empty, so the infimum below is an attained minimum
    and never the `sInf ∅ = 0` default. -/
theorem annihilatorDegrees_nonempty {d : ℕ} (P : Predicate d) :
    (annihilatorDegrees P).Nonempty := by
  by_cases h : ∀ x, P x = true
  · refine ⟨_, P, ⟨?_, Or.inr ?_⟩, rfl⟩
    · intro hP
      have := congrFun hP (fun _ => false)
      simp [h] at this
    · intro x
      simp [h x]
  · push Not at h
    obtain ⟨x0, hx0⟩ := h
    refine ⟨_, fun x => !P x, ⟨?_, Or.inl ?_⟩, rfl⟩
    · intro hf
      have := congrFun hf x0
      simp_all
    · intro x
      show (!P x && P x) = false
      cases P x <;> rfl

/-- Definition 3: AI(P) = min{deg f : f ≢ 0, f P ≡ 0 or f (P ⊕ 1) ≡ 0}. -/
noncomputable def algebraicImmunity {d : ℕ} (P : Predicate d) : ℕ :=
  sInf (annihilatorDegrees P)

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. 3 (PDF p. 4) symmetric predicates; p. 5 (PDF p. 6), Definition 3

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me