What is the proof that the existence of one-way-functions implies $P \neq NP$?

Question

I am not an expert in this field, but I have read that the existence of one-way functions implies $P \neq NP$. Since there seem to be so many different definitions of one-way-functions and I have not seen a proof I wanted to ask if someone knows where to read this, or knows the proof. Please if you give a proof, also give a precise definition of which version of "one-way-function" you use. The proof can of course be detailed, the detailed, the better! :) Thanks!

Answer 1

$P \ne NP$ if and only if worst-case one-way functions exist.

Reference:

Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical systems theory, 25(3):203–221, 1992.

Answer 2

If P=NP, every polytime computable 1-1 function $f$ has a polytime computable inverse: $\{(x,y) \mid \exists z\ |yz| \leq poly(|x|) \land f(yz)=x \}$ is NP. We can find a $y$ such that $f(y)=x$ by starting with the empty string as$y$ and greedily adding the following bits using this NP oracle.

Answer 3

Let $f:\{0,1\}^* \rightarrow \{0,1\}^*$ be a OWF and define $L_f = \{(x,y)\in \{0,1\}^* \times \{0,1\}^*:$ there exists $z$ such that $f(xz)=y\}$. I construct the following non-deterministic Turing machine: $A((x,y)):$"Non-deterministically guess $z$. return ACCEPT if $f(xz)=y$ and REJECT otherwise" $A$ makes a single call to $f$ which is OWF and therefore runs in polynomial time. $A$ decides $L_f$ therefore $L_f \in NP$.

Assuming $P=NP$, there exists a deterministic polynomial time decider $A'$ such that $A'((x,y)) = ACCEPT \iff A((x,y)) = ACCEPT$. Using $A'$ I construct $f'$ which inverts $f$ in deterministic polynomial time. First, I define a helper function $h:(\{0,1\}^*,\{0,1\}^*) \rightarrow \{0,1\}^*$ the following way:

$h(x,y) = $ \begin{cases} h(x0,y),& \text{if } A'(x0, y) = ACCEPT\\ h(x1,y),& \text{if } A'(x1, y) = ACCEPT\\ x & \text{otherwise} \end{cases}

$h$ is a recursive function that tries to add a single bit $b$ to $x$ in every iteration. If $A'$ accepts $xb$, that means there exists some $z$ such that $f(xbz) = y$. In this case, $h$ recalls itself with $xb$. Once $|z| = 0$ I know parameter $x$ contains the preimage of $y$ and the DTM $A'$ would reject both $(x0,y)$ and $(x1,y)$. In this case $h$ returns $x$. $h$ runs in deterministic polynomial time in $|xz|$ since at every iteration $|x|$ grows by 1 on account of $|z|$. At every iteration $h$ calls $A'$ which runs in polynomial time, making the total runtime of $h$ polynomial.

Using $h$ I define the function $f':\{0,1\}^* \rightarrow \{0,1\}^*$ such that $f'(y) = $ "Initialize $x$ to be empty and return $h(x,y)$". $f'$ inverts $f$ in deterministic polynomial therefore $f$ is not OWF, reaching contradiction. In conclusion, if there exists a OWF, then $P \neq NP$.