Question

prove that if P=NP then one way functions do not exist

Answer 1

It is easier to prove that P=NPP=NP implies one-way functions do not exist:

Let P=NPP=NP, and assume ff is one-way. Then consider the language LL of pairs (x∗,y)(x∗,y) such that x∗x∗ is a prefix of some xxsatisfying f(x)=yf(x)=y. LL is in NPNP because xx itself is a witness 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=NPP=NP, and we can use a decider DD for LL to "invert" yy. Receiving the input (y,1n)(y,1n) (nn being the safety parameter), start with the pair (ε,y)(ε,y), i.e. with the empty word as a prefix, and use DD to incrementally add bits to the prefix part until you obtain (x,y)(x,y) with f(x)=yf(x)=y. Such an algorithm runs in poly time because it is guaranteed there exists an inverse image to yy of length at most nn. It follows that ff is not one-way, and we have a contradiction.