4 ms·

I'm a little surprised we didn't have decent quantum-resistant crypto even 20 years ago. All our public key crypto is based on the hardness of integer factoring

I'm a little surprised we didn't have decent quantum-resistant crypto even 20 years ago. All our public key crypto is based on the hardness of integer factoring and the discrete logarithm problem, neither of which are known to be NP-complete or NP-hard. Quantum computers can efficiently solve those two problems, but they haven't been shown to be able to handle any NP-complete problems. There have been previous attempts to make cryptosystems based on NP-complete problems like the knapsack problem, but never became as popular as RSA. Anyone have any guesses why we didn't see any popularly used crypto based on the hardness of, say, 3SAT or the knapsack problem?

dboreham 9y ago
Three Letter Agencies?
- openasocket 9y ago
  I was hoping for an explanation about how some of those NP-complete problems have a large class of edge cases that make them vulnerable, or maybe that it's difficult to design protocols that use them. I wasn't hoping for a conspiracy theory.
hannob 9y ago
People tried and it didn't work very well, see e.g.: https://en.wikipedia.org/wiki/Knapsack_cryptosystems https://en.wikipedia.org/wiki/Knapsack_cryptosystems It seems it's just really hard to create a new public key crypto system, so people sticked to what works as long as the quantum threat didn't sound too scary. Now it sounds scary enough that people look for alternatives.
- tptacek 9y ago
  To add to this: It's still sort of just scary in the abstract. There's no evidence that a quantum computer that could attack even weak incarnations of DH or RSA are within the realm of feasibility, and if things break in engineering's favor over the next decade we still probably won't be there. It's possible that me might never get there! The big problem is that there's a chance (a low chance) that we might get there within the (long) lifespan of our existing public key algorithms. There's a mindset in cryptography engineering that we design for secrets that must be kept for many decades. So: the "plausible" threat we face here is decades-hence retroactive decryption. It's useful to keep this in mind when doing security engineering, because PQ isn't "free": we have to trade things off to get it. It's possible that the modern PQ schemes we're pursuing will have grave flaws that put them within reach of classical cryptanalysis within just a few years. Even more importantly, it's not only possible but likely that there are implementation errors --- like using schoolbook RSA, or failing to validate a curve point --- that we won't fully understand for a decade after we adopt a new PQ scheme. And, just to make things more fun, we're not looking at 1 PQ scheme but at 3-4, some of them entirely unrelated to each other. Against all this you should also keep in mind the other forces that push PQ to the front of the field of cryptography's consciousness. Most serious cryptography is done academically. PQ has created a gold rush of paper topics. Naturally, it's going to seem super important if you pay attention to IACR ePrints. If what you're trying to protect are conventional financial transactions, or the integrity of applications running today that will have been rebooted at least once before 2050, there's a good chance that PQ is bad engineering for you.
jcranmer 9y ago
What you need for cryptography is to be able to reliably generate hard instances. It's actually easy to factor most numbers--½ of all numbers are divisible by 2, and ⅓ of all numbers are divisible by 3. What's difficult is factoring products of similar-sized primes, and generating arbitrarily large primes is fairly easy. When you look at, say, graph coloring or graph isomorphism, it turns out that most named classes of such graphs turn out to be fairly easily solved, which means generating the instances that can't be solved easily is difficult.

dboreham 9y ago

Three Letter Agencies?

openasocket 9y ago
I was hoping for an explanation about how some of those NP-complete problems have a large class of edge cases that make them vulnerable, or maybe that it's difficult to design protocols that use them. I wasn't hoping for a conspiracy theory.

hannob 9y ago

People tried and it didn't work very well, see e.g.: https://en.wikipedia.org/wiki/Knapsack_cryptosystems https://en.wikipedia.org/wiki/Knapsack_cryptosystems It seems it's just really hard to create a new public key crypto system, so people sticked to what works as long as the quantum threat didn't sound too scary. Now it sounds scary enough that people look for alternatives.

tptacek 9y ago
To add to this: It's still sort of just scary in the abstract. There's no evidence that a quantum computer that could attack even weak incarnations of DH or RSA are within the realm of feasibility, and if things break in engineering's favor over the next decade we still probably won't be there. It's possible that me might never get there! The big problem is that there's a chance (a low chance) that we might get there within the (long) lifespan of our existing public key algorithms. There's a mindset in cryptography engineering that we design for secrets that must be kept for many decades. So: the "plausible" threat we face here is decades-hence retroactive decryption. It's useful to keep this in mind when doing security engineering, because PQ isn't "free": we have to trade things off to get it. It's possible that the modern PQ schemes we're pursuing will have grave flaws that put them within reach of classical cryptanalysis within just a few years. Even more importantly, it's not only possible but likely that there are implementation errors --- like using schoolbook RSA, or failing to validate a curve point --- that we won't fully understand for a decade after we adopt a new PQ scheme. And, just to make things more fun, we're not looking at 1 PQ scheme but at 3-4, some of them entirely unrelated to each other. Against all this you should also keep in mind the other forces that push PQ to the front of the field of cryptography's consciousness. Most serious cryptography is done academically. PQ has created a gold rush of paper topics. Naturally, it's going to seem super important if you pay attention to IACR ePrints. If what you're trying to protect are conventional financial transactions, or the integrity of applications running today that will have been rebooted at least once before 2050, there's a good chance that PQ is bad engineering for you.

jcranmer 9y ago

What you need for cryptography is to be able to reliably generate hard instances. It's actually easy to factor most numbers--½ of all numbers are divisible by 2, and ⅓ of all numbers are divisible by 3. What's difficult is factoring products of similar-sized primes, and generating arbitrarily large primes is fairly easy. When you look at, say, graph coloring or graph isomorphism, it turns out that most named classes of such graphs turn out to be fairly easily solved, which means generating the instances that can't be solved easily is difficult.