No fully-black-box reduction from NP to size-verifiable OWF

Unconditional · against fully-black-box reductions · BB15

Statement

If a language $L$ reduces to inverting an efficiently computable, approximately size-verifiable function $f$ by a randomized polynomial-time reduction that may adapt its queries and works with every deterministic inversion oracle for $f$, then $L\in \mathbf{AM}\cap \mathbf{coAM}$ — BB15. For NP-complete $L$ this gives $\mathbf{NP}\subseteq \mathbf{coAM}$, equivalently $\mathbf{coNP}\subseteq \mathbf{AM}$, which collapses the polynomial hierarchy to its second level — BHZ87. A reduction of $\mathbf{NP}$ to inverting $f$ on average works in particular with every exact deterministic inverter, so the one-wayness of a size-verifiable function cannot be based on $\mathbf{NP}$-hardness by such a reduction unless $\mathbf{coNP}\subseteq \mathbf{AM}$.

Notes

• This recovers, for size-verifiable functions, the adaptive claim of AGGM06, which its authors retracted — AGGM10; for general functions only the non-adaptive barrier stands (No reduction from NP to OWF) — AGGM06.
• For one-way permutations and deterministic reductions the consequence strengthens to $\mathbf{NP}=\mathbf{coNP}$ (No deterministic reduction from NP to OWP) — Bra79b.