One way functions and P = NP?

Question

How can I show that no one way functions exist under assumption of P = NP?

Answer 1

If one way function exist, you can not prove your proposition!

It is better that ask:

Can we reduce the existance on OWF to P vs NP problem?

Andrej Bogdanov give a negative result. He show that non-adaptive reduction is not sufficient.

This problem in fact is a reduction from average case complexity to worst case complexity. You can see the monograph by Bogdanov and Trevisan.

Answer 2

While we don't know whether $P\neq NP$ implies the existence of (cryptographic) one-way functions (OWFs), we do know that $P=NP$ implies their absence.

The standard argument goes like this: Assume there is a candidate OWF $f$, define the language $L_f:=\{(y,z)|\exists x:f(x)=y\land z\text{ is a prefix of }x\}$. Clearly $L_f$ is in NP as you can easily verify the condition on $(x,y,z)$ (as well as their syntactic correctness) in polynomial time, especially since we demand OWFs to be computable in polynomial time.

But given that $P=NP$ there is a polynomial-time algorithm to decide $L_f$. This then allows us to start with $z=\varepsilon$ - the empty string - and then query our polynomial-time algorithm with $z\|1$ and $z\|0$ and choosing the extension of $z$ as our new $z$ which yielded a positive result. If both give negative results we should be done and return $z$.