6
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Joel David Hamkins
    Commented Oct 20, 2011 at 17:48
  • $\begingroup$ 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. $\endgroup$
    – mhum
    Commented Oct 20, 2011 at 20:05
  • $\begingroup$ 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. $\endgroup$
    – mhum
    Commented Oct 20, 2011 at 20:54
  • $\begingroup$ It seems as though the 'best' outcome is an oracle with respect to which $P\neq NP$ and yet OWFs don't exist. That wouldn't show anything about 'our' world, but it would serve to show the relative independence of the two notions. $\endgroup$
    – Steven Stadnicki
    Commented Jan 24, 2017 at 19:46
1
$\begingroup$

Complexity theory has a another notion of one-way functions: worst-case one-way functions.

It is known that $P \ne NP$ if and only if worst-case one-way functions exist.

Worst-case one-way functions exist if and only if there is injective length-increasing polynomial-time computable function that can not be inverted in polynomial-time.

Reference:

Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical systems theory, 25(3):203–221, 1992.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .