<p>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 <em>worst-case</em> 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$ <em>in the image of $f$</em> and $g(y)=0$ otherwise - there is a more precise answer. Namely, worst-case one-way functions exist <em>if and only if</em> $\mathsf{P} \neq \mathsf{UP}$. </p>

<p>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 <em>related</em> 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.</p>

CC BY-SA 3.0
2015-05-25T15:05:59.407Z
@RickyDemer: Whoops, I didn't mean to imply surjectivity. Fixed.
Joshua Grochow
CC BY-SA 3.0
2015-05-25T22:02:47.813Z
@RickyDemer I think Josh is referring to a result by Grollman and Selman. I do not know the result very well, but I think their definition of one-way function also requires that the function is injective.
Sasho Nikolov
CC BY-SA 3.0
2015-05-25T22:10:58.077Z
After looking at http://www.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.
Sasho Nikolov
CC BY-SA 3.0
2015-05-26T16:48:02.167Z
@RickyDemer: When $f$ is injective, the range of $f$ - i.e. $\{ x : (\exists y)[f(y)=x]\}$ - is a language in $\mathsf{UP}$.
Joshua Grochow
CC BY-SA 3.0
2015-05-24T18:43:41.457Z
2015-05-25T15:05:57.177Z
2015-05-25T15:05:57.177Z
Joshua Grochow
<p>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. </p>

<p>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):</p>

<p><a href="http://www.wisdom.weizmann.ac.il/~oded/p_aggm.html" rel="nofollow">http://www.wisdom.weizmann.ac.il/~oded/p_aggm.html</a></p>

CC BY-SA 3.0
2015-05-23T06:46:58.643Z
@PhilipWhite we'd be somewhere between Heuristica and Pessiland then, I guess: https://cseweb.ucsd.edu/~russell/average.ps
Sasho Nikolov
CC BY-SA 3.0
2015-05-22T23:28:43.697Z
2015-10-06T15:23:05.393Z
2015-10-06T15:23:05.393Z
Or Meir
<p>Is there a conditional impossibility result or the question is completely open?</p>

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

(Asked by: username_0 on 2015-05-22)

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

**Tags:** one-way-function

---

## 2 answers

### Answer by username_3 on 2015-05-22. Score: 16 | Accepted answer

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>

> **Comments:**
> **username_2**: @PhilipWhite we'd be somewhere between Heuristica and Pessiland then, I guess: https://cseweb.ucsd.edu/~russell/average.ps  

---

### Answer by username_1 on 2015-05-24. Score: 10

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.

> **Comments:**
> **username_1**: @RickyDemer: Whoops, I didn't mean to imply surjectivity. Fixed.  
> **username_2**: @RickyDemer I think Josh is referring to a result by Grollman and Selman. I do not know the result very well, but I think their definition of one-way function also requires that the function is injective.  
> **username_2**: After looking at http://www.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.  
> **username_1**: @RickyDemer: When $f$ is injective, the range of $f$ - i.e. $\{ x : (\exists y)[f(y)=x]\}$ - is a language in $\mathsf{UP}$.  

---

