# The significance of NP-Hard Problems in Cryptography

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.

• 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" :). – Gopi Oct 25 '11 at 9:23
• 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. – M.S. Dousti Oct 25 '11 at 9:51
• (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. – Tsuyoshi Ito Oct 25 '11 at 11:25
• 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. – Sasho Nikolov Oct 25 '11 at 18:20
• – Ciro Santilli 郝海东冠状病六四事件法轮功 Jul 10 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.