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.

Improve this 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
    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$
    – Sadeq Dousti
    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$
    – Tsuyoshi Ito
    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$
    – Sasho Nikolov
    Oct 25, 2011 at 18:20
  • $\begingroup$ Related: cs.stackexchange.com/questions/356/… $\endgroup$
    – Ciro Santilli OurBigBook.com
    Jul 10, 2020 at 17:44

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
1

Your Answer

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

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