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

<p>An excellent read is the classic by Russell Impagliazzo, <a href="http://cseweb.ucsd.edu/~russell/average.ps" rel="noreferrer">A Personal View of Average-Case Complexity</a>, 1995. </p>

<p>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</p>

CC BY-SA 3.0
2011-10-25T14:05:23.273Z
[These slides](http://notendur.hi.is/hh/kennsla/rrr/hhh-presentation.pdf) are a good introduction.
Aaron Sterling
CC BY-SA 3.0
2011-10-25T11:52:25.127Z
2011-10-25T15:33:32.130Z
2011-10-25T15:33:32.130Z
Mohammad Al-Turkistany
<p>I didn't refer any literature but thought this was ideal to get views from people here..</p>

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

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

<p>It would also be great if can suggest any interesting articles regarding this..</p>

<p>Thanks!</p>

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

CC BY-SA 3.0
2011-10-25T09:23:53.630Z
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
CC BY-SA 3.0
2011-10-25T09:51:55.100Z
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.
Sadeq Dousti
CC BY-SA 3.0
2011-10-25T11:25:26.643Z
(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
CC BY-SA 3.0
2011-10-25T18:20:21.957Z
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
CC BY-SA 4.0
2020-07-10T17:44:48.017Z
Related: https://cs.stackexchange.com/questions/356/why-hasnt-there-been-an-encryption-algorithm-that-is-based-on-the-known-np-hard
Ciro Santilli OurBigBook.com
<np-hardness><cr.crypto-security>
The significance of NP-Hard Problems in Cryptography
Maverickgugu
# The significance of NP-Hard Problems in Cryptography

(Asked by: username_0 on 2011-10-25)

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.

**Tags:** np-hardness, cr.crypto-security
> **Comments:**
> **username_1**: 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" :).  
> **username_2**: 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.  
> **username_3**: (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.  
> **username_4**: 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.  
> **username_5**: Related: https://cs.stackexchange.com/questions/356/why-hasnt-there-been-an-encryption-algorithm-that-is-based-on-the-known-np-hard  

---

## 1 answers

### Answer by username_6 on 2011-10-25. Score: 10

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](http://cseweb.ucsd.edu/~russell/average.ps), 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

> **Comments:**
> **username_7**: [These slides](http://notendur.hi.is/hh/kennsla/rrr/hhh-presentation.pdf) are a good introduction.  

---

