Welcome to MathOverflow

Question

1

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

flag	asked Oct 20 2011 at 2:44 anonymous coward 11●1

mhum · Answer 1 · 2011-10-20 17:19:41Z UTC

6

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.

edited Oct 20 2011 at 17:19

answered Oct 20 2011 at 4:22

mhum
385●1●7

	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 2011 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 2011 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 2011 at 20:54

P vs NP and OWFS

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.