How to show that a one-way function proves that P ≠ NP?

Question

According to this, the existence of a one-way function proves P ≠ NP. What is the proof of this?

One way to show this is that if P = NP, then any function is easy to invert. P and NP are about decision problems though, not computation problems.

(Basically, my question is about how statements about decision problems relate to computational problems.)

Answer 1

It is easier to prove that $P = \mathit{NP}$ implies one-way functions do not exist:

Let $P = \mathit{NP}$, and assume $f$ is one-way. Then consider the language $L$ of pairs $(x^\ast, y)$ such that $x^\ast$ is a prefix of some $x$ satisfying $f(x) = y$. $L$ is in $\mathit{NP}$ because $x$ itself is a witness (up to minor formal details; see this question too) we can use to verify the pair in only polynomial time—recall that a one-way function can be computed in poly-time.

But we have $P = \mathit{NP}$, and we can use a decider $D$ for $L$ to "invert" $y$. Receiving the input $(y, 1^n)$ ($n$ being the safety parameter), start with the pair $(\varepsilon, y)$, i.e. with the empty word as a prefix, and use $D$ to incrementally add bits to the prefix part until you obtain $(x,y)$ with $f(x) = y$. Such an algorithm runs in poly time because it is guaranteed there exists an inverse image to $y$ of length at most $n$. It follows that $f$ is not one-way, and we have a contradiction.

---

Regarding your question about the relation between decision problems and computational ones: the whole point of the $P = \mathit{NP}$ dilemma is answering whether computing a solution is as hard as simply verifying it or not. This is because non-determinism virtually allows us to "cheat" and circumvent wasting any time in computing the answer; we only need to guess it and check whether our guess was correct or not.

An interesting consequence of the statement above is that the assumption of one-way functions is actually stronger than $P \neq \mathit{NP}$. This is in line with the famous hierarchy of cryptographical assumptions known as Impagliazzo's five worlds.

Answer 2

Sounds like a homework problem. There is a solution here.

Informally, define a language L = { (x', y) s.t. x' <= x and f(x) == y }. Basically, it says x' is a prefix of x, and x is a preimage of y.

It's easy to see L is in NP, because when given x' and y, you can append bits to x' until it reaches x, then you have successfully verified. This only needs polynomial time on a nondeterministic TM.

If P == NP, then L is in P. This means, when given x' and y, you can tell in polynomial time, whether it's possible to append bits to x' so that x' finally becomes a preimage of y. Then you can start from an empty string, try appending 0 and do a test, try appending 1 and do a test, at least one of them will return true because empty string is surely a prefix of x. In the following rounds, the string x' is always a prefix of x because you know whether you should add 0 or 1. Finally x' will become x. Congrat: You have found x, which is a preimage of y, in polynomial time. This reverts f.