4
$\begingroup$

I didn't refer any literature but thought this was ideal to get views from people here..

Assuming that P=NP is proved would cryptography(only provable security) be impossible? Since the adversary can break any scheme in polynomial time.

Aren't the NP-hard problems enough to save the day? I've heard of crypto-systems based on "subset problems". Since P=NP would not affect the nature of NP-hard problems.

It would also be great if can suggest any interesting articles regarding this..

Thanks!

P.S: Please feel free to edit if you find any naive statements in the question.

$\endgroup$
5
  • $\begingroup$ Don't worry there are other complexity classes. If P=NP, then maybe a class (does it exist?) which used to say it is NP-hard to verify a solution, and in EXP to find it could be a good new way to "save the day" :). $\endgroup$
    – Gopi
    Commented Oct 25, 2011 at 9:23
  • $\begingroup$ Unless we change the notion of efficient computations, there would be no cryptography with P = NP. This is because honest parties are efficient (BPP) algorithms, and they can't use hard problems beyond NP (say, EXP) to foil the adversary. $\endgroup$ Commented Oct 25, 2011 at 9:51
  • 4
    $\begingroup$ (1) I doubt that what you call “crypto-systems based on ‘subset problems’” are based on the NP-hardness of any problems. (2) If P=NP, then every problem is NP-hard (under polynomial-time reducibility), and NP-hardness per se will become a useless notion. $\endgroup$ Commented Oct 25, 2011 at 11:25
  • $\begingroup$ On one hand I like how the OP is honest in admitting not doing any background research before asking the question. On the other hand, I think our site will be much more efficient if everyone does their best to answer questions on their own, before turning to the community. Even looking at the wiki entry for the P vs NP problem would partially answer your question. $\endgroup$ Commented Oct 25, 2011 at 18:20
  • $\begingroup$ Related: cs.stackexchange.com/questions/356/… $\endgroup$ Commented Jul 10, 2020 at 17:44

1 Answer 1

10
$\begingroup$

Hardness of NP-complete problems is not sufficient for cryptography. Even if NP-complete problems are hard in the worst-case (P≠NP ), they still could be efficiently solvable in the average-case. Cryptography assumes the existence of average-case intractable problems in NP. Also, proving the existence of hard-on-average problems in NP using the $P \ne NP$ assumption is a major open problem.

An excellent read is the classic by Russell Impagliazzo, A Personal View of Average-Case Complexity, 1995.

An excellent survey is Average-Case Complexity by Bogdanov and Trevisan, Foundations and Trends in Theoretical Computer Science Vol. 2, No 1 (2006) 1–106

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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