24 ms·
No crypto-problem is NP-complete. People tried that for a while, see https://en.wikipedia.org/wiki/Knapsack_cryptosystems https://en.wikipedia.org/wiki/Knapsac
by eru 3y ago
No crypto-problem is NP-complete. People tried that for a while, see https://en.wikipedia.org/wiki/Knapsack_cryptosystems https://en.wikipedia.org/wiki/Knapsack_cryptosystems but it didn't work.
> Or maybe there’s something about NP-complete problems that make them less amenable to be a valid crypto system?
To simplify a bit, the problem is that to work as a crypto system your particular problems needs to be both in NP and in co-NP. And we know of no problem that is both NP-complete and in co-NP. It's widely conjectured that there is no such problem. See https://en.wikipedia.org/wiki/Co-NP https://en.wikipedia.org/wiki/Co-NP that page even mentions integer factorisation.
That's why you can't just take the NP-complete problem itself as a basis for your cryptosystem, you have to pick some subset of instances that's also in co-NP. And apparently it's almost impossible for us to pick such a subset, but still have the instances be hard enough to solve on average.