i know that $P = NP \Rightarrow$ non existence of OWF. but i don't understand why the claim: $P \neq NP \Rightarrow$ existence of OWF is wrong?

An intuitive answer would be enough.

  • $\begingroup$ Where did you read that the claim is wrong? $\endgroup$ – mikeazo Nov 12 '16 at 13:24
  • $\begingroup$ the existence of a proof that P and NP are not equal would not directly imply the existence of one-way functions. wikipedia $\endgroup$ – odu9 Nov 12 '16 at 13:27
  • $\begingroup$ i would guess that : it's not sufficient for OWF to show that you can't solve for one input , but for np complete problem , its sufficient for just one input, but i want to make sure. $\endgroup$ – odu9 Nov 12 '16 at 13:29
  • 1
    $\begingroup$ The wikipedia article links to Goldwasser and Bellare's lecture notes. $\endgroup$ – mikeazo Nov 12 '16 at 14:40
  • $\begingroup$ I know I'm very late to the party, but aren't you asking why A => B <=/=> ~A => ~B? $\endgroup$ – J. Dionisio Jun 14 '20 at 16:09

an answer from Goldwasser and Bellare's lecture notes. 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, worst-case hardness is a poor measure of security. Security requires hardness on most cases or at least average-case hardness. Hence, a necessary condition for the existence of secure encryption schemes is the existence of languages in NP which are hard on the average. Furthermore, P≠ NP is not known to imply the existence of languages in NP which are hard on the average.

  • 1
    $\begingroup$ In addition, even a hard-on-average language in NP does not necessarily imply the existence of an "easy-to-compute and hard-to-invert" function. $\endgroup$ – Geoffroy Couteau Nov 12 '16 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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