I always found that part odd. I’d assume you would want the problem you build your crypto system built around to be NP-complete, since that would seem to put you on the firmest possible ground. And yet those are most likely not NP-complete, and I think the post-quantum systems proposed aren’t NP complete either.
Maybe being NP-complete isn’t as important as I realize? Or maybe there’s something about NP-complete problems that make them less amenable to be a valid crypto system?
> 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 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.
Maybe being NP-complete isn’t as important as I realize? Or maybe there’s something about NP-complete problems that make them less amenable to be a valid crypto system?