OWP inversion ∈ NP ∩ coNP

Inclusion · folklore

Statement

Inverting a one-way permutation is a problem in NP $\cap$ coNP: for every polynomial-time computable $f$ that permutes each $\{0,1{\}}^n$, the language $\{(y,i):1\le i\le |y|\text{ and the }i\text{-th bit of }{f}^{-1}(y)\text{ is }1\}$ is in $\mathbf{NP}\cap \mathbf{coNP}$ — folklore.

Sketch

Every $y$ has exactly one preimage $x$, and $x$ certifies membership when $x_i=1$ and non-membership when $x_i=0$; the condition $1\le i\le |y|$ is checked directly.

Notes

• With error amplification, a $\mathbf{BPP}$ algorithm for the language inverts $f$ on every $y$ bit by bit, so one-way permutations exist only if $\mathbf{NP}\cap \mathbf{coNP}⊈\mathbf{BPP}$ — folklore.
• A deterministic polynomial-time reduction from an $\mathbf{NP}$-complete language to this one gives $\mathbf{NP}=\mathbf{coNP}$ (No deterministic reduction from NP to OWP) — Bra79b.