Theorem 3 — vanishing bit-fixing affine advantage of MOD iff and balanced parities
OpenGoldreichAffine.Exponential.Supplement.modular_advantage_criterionboolean-functionscryptographyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix an integer and a residue set . Then
if and only if and
Here is the bit-fixing affine advantage at remaining inputs. The limit condition is: for every there is such that for all and all .
This companion theorem shows that vanishing bit-fixing affine advantage of a modular predicate requires a modulus divisible by four, which singles out as the smallest candidate modulus with unbounded degree.
Differences from the source:
- encoding: lim_{b′→∞} sup_{b≥b′} adv_{b′}(MOD_b^{t,S0}) = 0 → ∀ε>0 ∃B ∀b′≥B ∀b≥b′, |adv_{b′}(MOD_b^{t,S0})| ≤ ε; reason: for b′ ≤ b the advantage lies in [0,1/2] (an affine function and its complement are both affine), so the sup exists and tends to 0 exactly when eventually every term is at most ε
- encoding: |S0 ∩ 2Z| = |S0 ∩ (2Z+1)| = t/4, S0 ⊆ [t] → (S0.filter Even).card = t/4 ∧ (S0.filter Odd).card = t/4, S0 ⊆ Finset.range t; reason: same sets; t/4 is exact division once 4 ∣ t, which is the first conjunct
Preamble
import Definitions.Def_GoldreichAffine_Exponential_Supplement_Modular open MatousekLP.Codes (Word weight) set_option autoImplicit false
Formal statement
namespace GoldreichAffine.Exponential.Supplement
/-- Theorem 3, printed p.10 / PDF p.11: lim_{b'→∞} sup_{b≥b'} adv_{b'}(MOD^{t,S0}_b) = 0
iff 4 ∣ t and S0 has exactly t/4 even and t/4 odd residues. -/
theorem modular_advantage_criterion (t : ℕ) (S0 : Finset ℕ) (ht : 2 ≤ t)
(hS0 : S0 ⊆ Finset.range t) :
(∀ ε : ℝ, 0 < ε → ∃ B : ℕ, ∀ b' : ℕ, B ≤ b' → ∀ b : ℕ, b' ≤ b →
|advantage (modPredicate t S0 b) b'| ≤ ε) ↔
(4 ∣ t ∧ (S0.filter Even).card = t / 4 ∧ (S0.filter Odd).card = t / 4) := 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 3; proof App. B.2, pp. 27–29 (PDF pp. 28–30)