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..


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

  • $\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 Oct 25 '11 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$ – M.S. Dousti Oct 25 '11 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$ – Tsuyoshi Ito Oct 25 '11 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$ – Sasho Nikolov Oct 25 '11 at 18:20
  • $\begingroup$ Related: cs.stackexchange.com/questions/356/… $\endgroup$ – Ciro Santilli新疆棉花TRUMP BAN BAD Jul 10 '20 at 17:44

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


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.