Theorem 5 — every -input residual of MOD12 has algebraic immunity ≥ ⌊(b'+1)/3⌋
OpenGoldreichAffine.Exponential.Supplement.mod12_residual_algebraic_immunityboolean-functionscryptographyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and . For every residual ,
Consequently ; the upper half is , since the algebraic immunity of any Boolean function on inputs is at most .
This companion theorem shows that MOD12 keeps algebraic immunity linear in the number of free inputs under every partial fixing.
Differences from the source:
- encoding: b ≥ 6 and 6 ≤ b′ ≤ b → 6 ≤ b′ and b′ ≤ b; reason: b ≥ 6 follows from 6 ≤ b′ ≤ b
- encoding: AI(M′) ≥ ⌊(b′+1)/3⌋; consequently AI(M′) = Θ(b′) → (b′ + 1) / 3 ≤ AI M′ ∧ AI M′ ≤ b′; reason: natural division is the floor; the Θ consequence is the floor bound together with AI ≤ b′, the constant the proof gives (PDF p. 35)
Preamble
import Definitions.Def_GoldreichAffine_Exponential_Supplement_Modular import Definitions.Def_GoldreichAffine_Exponential_Supplement_Algebraic open MatousekLP.Codes (Word weight) set_option autoImplicit false
Formal statement
namespace GoldreichAffine.Exponential.Supplement
/-- Theorem 5, printed p.10 / PDF p.11: AI(M') ≥ ⌊(b'+1)/3⌋ for every M' ∈ R_{b'}(MOD12_b),
6 ≤ b' ≤ b; the second conjunct AI(M') ≤ b' is the upper half of AI(M') = Θ(b')
with the constant of the proof (PDF p.35). -/
theorem mod12_residual_algebraic_immunity (b b' : ℕ) (hb' : 6 ≤ b') (hbb : b' ≤ b)
(M' : Predicate b') (hM : IsResidual (mod12 b) M') :
(b' + 1) / 3 ≤ algebraicImmunity M' ∧ algebraicImmunity M' ≤ 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, p. 10 (PDF p. 11), Theorem 5; proof App. B.4, p. 34 (PDF p. 35)