Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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