Theorem 2 — subexponential cost iff bit-fixing affine advantage tends to 1/2
OpenGoldreichAffine.Exponential.Supplement.subexponential_cost_characterizationboolean-functionscryptographyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any family of Boolean predicates, on inputs, and fix reals and . Set output bits and nonlinear arity , let , and let be the optimal idealized cost of the guess-and-affine-approximation attack (Eq. (6)) against a seed of weight . Then
The left side means: for every there is such that for all the size parameters are valid and for every .
This companion theorem characterizes the subexponential regime of the cost model, complementing the mission's goal (Theorem 1), which characterizes the exponential regime.
Differences from the source:
- encoding: m = n^s, b = γ log₂ n and θb with integers implicitly rounded up → m = ⌈n^s⌉, b = ⌈γ log₂ n⌉, ⌈θb⌉ (the published base regime); reason: the paper's rounding convention of §2; the same definitions as the published goal
- encoding: C⋆(n,w;γ) = 2^{o(n)}, uniformly over w ∈ W_n (§3.3) → ∀ε>0 ∃N ∀n≥N, ValidSize s γ n ∧ ∀w ∈ W_n, log₂ C⋆ ≤ εn, with N before w; reason: log₂ C⋆ ≥ 0 holds in the cost model (C⋆ ≥ 1, App. A.5), so only the upper estimate carries content; ValidSize holds for all large n when s>1, γ>0
- encoding: γ > 0 a fixed constant of §3.3 → γ quantified outside the iff, with 0 < γ; reason: the theorem holds for each fixed γ (App. A.5: 'the argument holds for every fixed γ > 0')
Preamble
import Definitions.Def_GoldreichAffine_Exponential_Supplement_Regimes open scoped NNReal ENNReal open MatousekLP.Codes (Word weight) set_option autoImplicit false
Formal statement
namespace GoldreichAffine.Exponential.Supplement
/-- Theorem 2, printed p.8 / PDF p.9 (proof App. A.5, PDF pp.22–23): for each fixed gamma > 0,
C*(n,w;gamma) = 2^{o(n)} uniformly over W_n iff adv_{theta b}(M_b) → 1/2 for every theta in (0,1). -/
theorem subexponential_cost_characterization (M : PredicateFamily) (s γ : ℝ)
(hs : 1 < s) (hγ : 0 < γ) :
SubexponentialCost M s γ ↔ NearHalfAdvantage M := 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. 8 (PDF p. 9), Theorem 2; proof App. A.5, pp. 21–22 (PDF pp. 22–23)