No reduction from NP to OWF

Unconditional · AGGM06

Statement

For every polynomial-time computable $f$, a randomized non-adaptive reduction of NP to inverting $f$ on average implies $\mathbf{coNP}\subseteq \mathbf{AM}$ — AGGM06. The one-wayness of $f$ therefore cannot be based on worst-case $\mathbf{NP}$-hardness by such a reduction unless $\mathbf{coNP}\subseteq \mathbf{AM}$, which collapses the polynomial hierarchy to its second level — BHZ87.

Notes

• AGGM06 also claim the consequence for arbitrary (adaptive) reductions whenever $|f^{-1}(y)|$ is efficiently computable from $y$; the authors retracted that claim, and only the non-adaptive result stands — AGGM10.
• For size-verifiable one-way functions the adaptive case is recovered (No fully-black-box reduction from NP to size-verifiable OWF): a general (adaptive) reduction of $\mathbf{NP}$ to inverting such an $f$ implies $\mathbf{NP}\subseteq \mathbf{coAM}$ — BB15.