# P vs NP and OWFS

It is known (simple HW exercise) that:

If P = NP, that OWFs (one way functions) can not exist.

It is also known that there is a Universal OWF: namely, there is a function f: s.t. if any OWF exists, then f is a OWF. [This is a standard result of concatenating many functions.]

Question: Is the following question open: (P != NP) => (OWFs exist) ?

[And what is known about this question?]

Thanks

-

## 1 Answer

P != NP does not imply anything about the existence of one-way functions. From Goldwasser and Bellare's "Lecture Notes on Cryptography":

However, the above mentioned necessary condition (e.g.: P != NP) is not a sufficient one. P != NP only implies that the encryption scheme is hard to break in the worst case. It does not rule-out the possibility that the encryption scheme is easy to break in almost all cases. In fact, one can easily construct "encryption schemes" for which the breaking problem is NP-complete and yet there exist an efficient breaking algorithm that succeeds on 99% of the cases. Hence, worse-case hardness is a poor measure of security.

Also, two of Impagliazzo's worlds where P != NP, Heuristica and Pessiland, have no one-way functions while two others, Minicrypt and Cryptomania, do.

-
The claims made in your answer would seem to be statements of expectation, rather than mathematically proved assertions. For example, you say that "$P\neq NP$ does not imply anything...", but of course, if $P=NP$ happens to be true, an open question, then $P\neq NP$ would imply everything (as a false statement implies anything). In particular, the claim in your quotation that $P\neq NP$ is not a sufficient hypothesis is not actually proved there, for to prove that $P\neq NP$ is not a sufficient hypothesis for anything would imply that it is not false, and thus would settle $P$ versus $NP$. – Joel David Hamkins Oct 20 '11 at 17:48
Perhaps it is more accurate to say that $P\neq NP$ alone does not imply the existence of one-way functions? Or, that $P\neq NP$ is consistent with the existence of one-way functions and also consistent with the non-existence of one-way functions? My understanding is that the exact manner in which $P\neq NP$ determines the existence of one-way functions. Roughly, if NP problems are hard only in the worst-case but easy on average (for appropriate definitions of hard, easy, and average), OWF don't exist; if NP problems are hard on average, OWF may (but are not guaranteed to) exist. – mhum Oct 20 '11 at 20:05
I guess the unspoken assumption which should be spoken is "given our current knowledge". That is to say, as far as I know, we do not yet have any additional results that when combined with $P \neq NP$ implies either the existence or non-existence of one-way functions. Results in this line of investigation would likely be very interesting. – mhum Oct 20 '11 at 20:54