# What's known about basing one-way function on the $P \neq NP$ assumption?

Is there a conditional impossibility result or the question is completely open?

We cannot hope to prove a general impossibility result since if one-way functions exist (and we believe they do), then in particular it follows that the statement "If $P \ne NP$ then one-way functions exist" is true.

However, we can prove that certain proof techniques are too weak to prove that statement. In particular, the following paper of Akavia, Goldreich, Goldwasser and Moshkovitz proves that this statement cannot be proved by certain black-box reductions (conditioned on plausible assumptions):

http://www.wisdom.weizmann.ac.il/~oded/p_aggm.html

• What if P != NP and one-way functions do not exist, as might occur if NP = coNP?
– user1338
Commented May 23, 2015 at 1:47
• @PhilipWhite we'd be somewhere between Heuristica and Pessiland then, I guess: cseweb.ucsd.edu/~russell/average.ps Commented May 23, 2015 at 6:46

If you mean the cryptographic kind of one-way function (i.e. average-case hard to invert), then Or Meir's answer is great. But for the slightly easier notion of worst-case one-way function - that is, an injective function $f$ that is computable in polynomial time, but where there is no deterministic polynomial-time algorithm $g$ such that $f(g(y)) = y$ for all $y$ in the image of $f$ and $g(y)=0$ otherwise - there is a more precise answer. Namely, worst-case one-way functions exist if and only if $\mathsf{P} \neq \mathsf{UP}$.

So for worst-case one-way functions, your question essentially boils down to the relationship between $\mathsf{UP}$ and $\mathsf{NP}$. This relationship is essentially wide open, and there are oracles in both directions. A few relationships for related questions are known - namely, Valiant-Vazirani ($\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$) and Hemaspaandra-Naik-Ogihara-Selman ($\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$ implies $\mathsf{PH}$ collapses) - but I'm not aware of any direct, unconditional relationship that deals with $\mathsf{NP}$ and $\mathsf{UP}$ precisely.

• That's an ... odd definition for worst-case onewayness. $\:$ (In particular, it implies surjectivity.) $\hspace{.38 in}$ I would've expected it to mirror the cryptographic definition more closely. $\hspace{1.63 in}$
– user6973
Commented May 25, 2015 at 4:28
• @RickyDemer: Whoops, I didn't mean to imply surjectivity. Fixed. Commented May 25, 2015 at 15:05
• How is $\operatorname{UP}$ involved? $\:$ (Consider the function given by sending pairs [SAT_instance,satisfying_assignment] to their encoded SAT_instance, and everything else to something that's not a SAT instance.) $\;\;\;\;$
– user6973
Commented May 25, 2015 at 20:26
• After looking at sciencedirect.com/science/article/pii/0304397585900854, the definition for a worst case one way function seems to be: 1) $f$ is an injection, 2) $x$ and $f(x)$ are polynomially related in size, 3) $f(x)$ is polytime computable, 4) $f^{-1}(y)$ is not polytime computable for all $y$ in the range. Commented May 25, 2015 at 22:10
• @RickyDemer: When $f$ is injective, the range of $f$ - i.e. $\{ x : (\exists y)[f(y)=x]\}$ - is a language in $\mathsf{UP}$. Commented May 26, 2015 at 16:48