Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.