There is any cryptography system that have a good reputation based on NP complete problem? I read about the knapsack, but it was cracked.


1 Answer 1


No, the problem is np-completeness or even np-hardness is a worst case thing. In crypto, we don't want our systems to be unbreakable only in the worst case. We want them to be unbreakable at least in the average case. It would be better if it were unbreakable in the best case (or all cases).

Another, related, issue we have is that of generating hard instances of the problem. NP-completeness does not guarantee that we can easily generate hard instances of the problem. Compare this with factoring where we can easily generate hard to factor numbers.

There have been a few other good, related questions on SE that you might find interesting:

I won't summarize them here. They are definitely worth a read though.


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.