No deterministic reduction from NP to OWP

Unconditional · Bra79b

Statement

If an NP-complete language reduces to inverting a polynomial-time computable permutation $f$ by a deterministic polynomial-time, possibly adaptive, oracle reduction, then $\mathbf{NP}=\mathbf{coNP}$ — Bra79b, in the form usually cited — GG98, AGGM06. A reduction to inverting $f$ on average works in particular with the exact inverter, so the one-wayness of a one-way permutation cannot be based on $\mathbf{NP}$-hardness by such a reduction unless $\mathbf{NP}=\mathbf{coNP}$.

Sketch

For a permutation $f$ of each $\{0,1{\}}^n$, the language $\{(y,i,b):\text{the }i\text{-th bit of }{f}^{-1}(y)\text{ is }b\}$ lies in $\mathbf{NP}\cap \mathbf{coNP}$, with the preimage of $y$ as certificate either way. A deterministic reduction answers its oracle queries through this language, so $\mathrm{SAT}\in {\mathbf{P}}^{\mathbf{NP}\cap \mathbf{coNP}}=\mathbf{NP}\cap \mathbf{coNP}$ — standard.

Notes

• Brassard states the claim for public-key encryption with a deterministic encryption algorithm whose valid public keys form a $\mathbf{coNP}$ set; GG98 review and extend it — GG98.
• For randomized adaptive reductions, a one-way permutation is size-verifiable, so such a reduction gives $\mathbf{coNP}\subseteq \mathbf{AM}$ (No fully-black-box reduction from NP to size-verifiable OWF) — BB15.