OWF inversion ∈ NP

Inclusion · folklore

Statement

Inverting a one-way function is a problem in NP: for every polynomial-time computable $f$, the language $\{(1^n,y,z):\exists x\in \{0,1{\}}^n\text{ with prefix }z\text{ and }f(x)=y\}$ is in $\mathbf{NP}$, with $x$ as certificate, and likewise for a keyed family with the key part of the instance — folklore.

Notes

• With error amplification, a $\mathbf{BPP}$ algorithm for the language inverts $f$ on every image by prefix search, so one-way functions exist only if $\mathbf{NP}⊈\mathbf{BPP}$, and one-way functions secure against non-uniform adversaries exist only if $\mathbf{NP}⊈P/poly$ — folklore.