Theorem 6.11 — a high-success non-deterministic algorithm for Avoid from one-way permutations
OpenAvoidPlast.Supplement.theorem_6_11average-case-complexitycomplexity-theorycryptographyp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1range-avoidancespace-bounded-computation
If sub-exponentially secure strong one-way permutations exist (Definition 6.10), then for some there is a non-deterministic polynomial-time algorithm using only non-deterministic bits such that for every family stretching bits to bits and evaluable in time , for infinitely many ,
in the sense of Theorem 6.9.
Differences from the source:
- encoding: → a negligible chosen after ; reason: the mission's reading R1
- encoding: (Definition 6.10) → ; reason: the same event, since is a permutation
- generalization: "evaluable in time " → evaluable in time ; reason: more families are covered; the proof's inverter runs in time , which absorbs the constant
- encoding: lengths → ; reason: the mission's reading R3
Preamble
import Mathlib import Definitions.Def_QuantumPRC_Negligible import Definitions.Def_AvoidPlast_Machine import Definitions.Def_AvoidPlast_ceilPow import Definitions.Def_AvoidPlast_prob import Definitions.Def_AvoidPlast_Supplement_IsPolyNTime import Definitions.Def_AvoidPlast_Supplement_SolvesAvoidNDB import Definitions.Def_AvoidPlast_Supplement_EvaluableInTime import Definitions.Def_AvoidPlast_Supplement_expBound import Definitions.Def_AvoidPlast_Supplement_SubexpStrongOWP
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 6.11, a high-success non-deterministic algorithm from one-way permutations (Li–Tell, *Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance*, STOC 2027 submission manuscript (sha256 e1ff3a9e…d6728),
p.38). If sub-exponentially secure strong one-way permutations exist (Definition 6.10), then for
some `ε > 0` there is a non-deterministic polynomial-time `A` using only `n^ε` non-deterministic bits
such that for every family `C` stretching `|x|^{ε²}` bits to `|x|^ε` bits and evaluable in time
`2^{|x|^{ε²}}`, for infinitely many `n`, `Pr_{x∈{0,1}^n}[A(x) solves Avoid(C_x)] ≥ 1 - n^{-ω(1)}` (in
the sense of Theorem 6.9).
**Formalization Note** `n^{-ω(1)}` is a negligible `ν` chosen after `C` (reading R1). -/
theorem theorem_6_11 (h : SubexpStrongOWP) :
∃ ε : ℝ, 0 < ε ∧ ∃ (A : Machine 2) (a : ℕ), IsPolyNTime A a ∧
∀ C : List Bool → List Bool → List Bool,
EvaluableInTime C (ceilPow (ε ^ 2)) (ceilPow ε) (expBound (ε ^ 2)) →
∃ ν : ℕ → ℝ, QuantumPRC.Negligible ν ∧ ∃ᶠ n : ℕ in Filter.atTop, 1 - ν n ≤
prob n (SolvesAvoidNDB A C (ceilPow (ε ^ 2)) (ceilPow ε) (ceilPow ε)) := 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 6.11, p.38 (PDF p.40)