Subexponential cost and near-half bit-fixing affine advantage (Theorem 2)
DefinitionGoldreichAffine_Exponential_Supplement_RegimesFix a predicate family , a real and a real . As in the published asymptotic regime of this mission, set , , and let be the typical seed weights. Write for the optimal idealized cost of the guess-and-affine-approximation attack with these parameters.
Subexponential cost (for this fixed ) means that uniformly over : for every there is such that for all the size parameters are valid and
Near-half advantage means that for every fixed ,
where is the published bit-fixing affine advantage (Definition 5).
These two properties are the two sides of Theorem 2.
Formalization Note The threshold is chosen before , which is the uniformity over required in §3.3. The logarithm is the published extended on , so an infinite cost never satisfies the bound. Only the upper estimate is written: holds in the cost model (App. A.5), so needs no clause. Here is rounded up, , following the paper's rounding convention (§2). Unlike the published ExponentialCostProperty, which quantifies over all internally, the cost property here is for one fixed .
import Definitions.Def_GoldreichAffine_Exponential_Asymptotic
open scoped NNReal ENNReal
open MatousekLP.Codes (Word weight)
set_option autoImplicit false
namespace GoldreichAffine.Exponential.Supplement
/-- Theorem 2 (printed p.8 / PDF p.9), cost side, for one fixed gamma:
log₂ C*(n,w;gamma) ≤ eps·n eventually, with N chosen before w (uniform over W_n).
The base regime (m = ⌈n^s⌉, b = ⌈gamma log₂ n⌉, ValidSize) is reused unchanged. -/
noncomputable def SubexponentialCost (M : PredicateFamily) (s γ : ℝ) : Prop :=
∀ ε : ℝ, 0 < ε → ∃ N : ℕ, ∀ n : ℕ, N ≤ n → ValidSize s γ n ∧
∀ w : ℕ, TypicalWeight n w →
logCost (asymptoticCost M s γ n w) ≤ (((ε * (n : ℝ)) : ℝ) : EReal)
/-- Theorem 2, advantage side: adv_{⌈theta b⌉}(M_b) → 1/2 for every theta in the OPEN interval (0,1). -/
noncomputable def NearHalfAdvantage (M : PredicateFamily) : Prop :=
∀ θ : ℝ, 0 < θ → θ < 1 → ∀ ε : ℝ, 0 < ε → ∃ B : ℕ,
∀ b : ℕ, B ≤ b → 1 ≤ b → |advantage (M b) (remainingArity θ b) - 1 / 2| < ε
end GoldreichAffine.Exponential.Supplement