There is any cryptography system that have a good reputation based on NP complete problem? I read about the knapsack, but it was cracked.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.