Theorem 7.11 — an average-case targeted HSG from one-way functions
OpenAvoidPlast.Supplement.theorem_7_11complexity-theorycryptographyhitting-set-generatorsp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computation
If sub-exponentially secure one-way functions exist, there are constants , and a non-deterministic polynomial-time algorithm that on uses at most non-deterministic bits and outputs on every accepting path strings of length , such that for every coAM procedure whose deterministic verifier runs in time and uses random and witness bits: for infinitely many , with probability at least over , if
then has an accepting path, and every accepting path outputs a string with .
Differences from the source:
- reading: "sub-exponentially secure one-way functions" (no definition in the paper) → Definition 6.10 without the permutation: polynomial-time , , every inverter of time inverts with negligible probability for large ; reason: this is the security the proofs of Theorems 6.9 and 7.11 contradict (an inverter of time for every )
- reading: , → constants before with and for every large ; reason: asymptotic notation with explicit constants
- encoding: time , random and witness bits → time ; exactly random and witness bits; reason: reading R3
- encoding: → Definition 7.4: ; reason: the paper's definition
Preamble
import Mathlib import Definitions.Def_AvoidPlast_Accepts import Definitions.Def_AvoidPlast_HaltsWithin import Definitions.Def_AvoidPlast_Machine import Definitions.Def_AvoidPlast_ceilPow import Definitions.Def_AvoidPlast_output import Definitions.Def_AvoidPlast_prob import Definitions.Def_AvoidPlast_Supplement_IsPolyNTime import Definitions.Def_AvoidPlast_Supplement_blockOf import Definitions.Def_AvoidPlast_Supplement_expBound import Definitions.Def_AvoidPlast_Supplement_SubexpOWF import Definitions.Def_AvoidPlast_Supplement_coAMOne
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 7.11, an average-case targeted HSG from cryptography (Li–Tell, *Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance*, STOC 2027 submission manuscript (sha256 e1ff3a9e…d6728), p.45). If
sub-exponentially secure one-way functions exist, there are `ε ∈ (0,1)`, `c > 0` and a
non-deterministic polynomial-time `H` that on `x ∈ {0,1}^n` uses at most `n^ε` non-deterministic
bits and outputs on every accepting path `L(n) = n^{O(ε)}` strings of length `m(n) = Θ(n^{ε²})`,
such that for every coAM procedure `D` whose deterministic verifier `D(x, y, ρ, w)` runs in time
`2^{n^{ε²}}` with `r_D = w_D = n^{ε³}` random and witness bits: for infinitely many `n`, with
probability at least `n^{-c}` over `x ∈ {0,1}^n`, if `Pr_y[D(x, y) = 1] ≥ 1 - 2^{m(n)^ε - m(n)}` then
`H(x)` has an accepting path and every accepting path outputs a string `y` with `D(x, y) = 1`.
**Formalization Note** The constants in `n^{O(ε)}` and `Θ(n^{ε²})` are existential before `D`;
both bounds hold for every sufficiently large `n`. `D(x, y) = 1` is Definition 7.4 (`coAMOne`). -/
theorem theorem_7_11 (h : SubexpOWF) :
∃ ε : ℝ, 0 < ε ∧ ε < 1 ∧ ∃ c : ℝ, 0 < c ∧
∃ (H : Machine 2) (a : ℕ) (L m : ℕ → ℕ) (b b₁ b₂ : ℝ), IsPolyNTime H a ∧
(∀ᶠ n : ℕ in Filter.atTop, (L n : ℝ) ≤ (n : ℝ) ^ (b * ε)) ∧
0 < b₁ ∧ (∀ᶠ n : ℕ in Filter.atTop,
b₁ * (n : ℝ) ^ (ε ^ 2) ≤ m n ∧ (m n : ℝ) ≤ b₂ * (n : ℝ) ^ (ε ^ 2)) ∧
(∀ x w : List Bool, w.length ≤ ceilPow ε x.length → Accepts H ![x, w] →
(output H ![x, w]).length = L x.length * m x.length) ∧
∀ D : Machine 4,
(∀ x y ρ w : List Bool, y.length = m x.length → ρ.length = ceilPow (ε ^ 3) x.length →
w.length = ceilPow (ε ^ 3) x.length →
HaltsWithin D ![x, y, ρ, w] (expBound (ε ^ 2) x.length)) →
∃ᶠ n : ℕ in Filter.atTop, (n : ℝ) ^ (-c) ≤ prob n fun x =>
1 - (2 : ℝ) ^ ((m n : ℝ) ^ ε - m n) ≤
prob (m n) (fun y => coAMOne D (ceilPow (ε ^ 3)) (ceilPow (ε ^ 3)) x y) →
(∃ w : List Bool, w.length ≤ ceilPow ε n ∧ Accepts H ![x, w]) ∧
∀ w : List Bool, w.length ≤ ceilPow ε n → Accepts H ![x, w] →
∃ i < L n, coAMOne D (ceilPow (ε ^ 3)) (ceilPow (ε ^ 3)) x
(blockOf (output H ![x, w]) (m n) i) := by sorry
end AvoidPlast.Supplement
Source
Li–Tell, Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance, STOC 2027 submission (manuscript sha256 e1ff3a9e…), Theorem 7.11, p.45 (PDF p.47)