6 ms·

A Tricky Path to Quantum-Safe Encryption

37 points by retupmoc01 11y ago

tptacek 11y ago
This stuff is all very interesting but, unless you're a researcher, has no immediate practical impact. What you would almost definitely accomplish by switching from (quantum cryptanalysis vulnerable) Curve25519 to a (supposed quantum safe) lattice or code-based algorithm is shipping something terribly insecure. It took a long time after the deployment of RSA, and an even longer time after ECC, to figure out the fiddly details of implementing it safely.
- jackgavigan 11y ago
  Why would you switch from one to t'other? Why not use both? That way, you get the best of both options that are available today.
  - sp332 11y ago
    In terms of usability and compatibility, you get the worst of both worlds. And if we take it as given that current QSE implementations are weak, it's not going to add much security.
    - jackgavigan 11y ago
      In the context of PQ crypto, the primary objective is to implement a cryptosystem that is more resistant to cryptanalysis by quantum computer than a non-QSE algorithms like RSA. If that is indeed one's primary objective, usability and compatibility are far lesser concerns. We can't say for certain whether any cryptosystem will prove to be strong, particularly in the face of a theoretical/hypothetical technology like quantum computing, but it seems logical to assume that, until it is broken, there exists at least some possibility that it will turn out to be strong. There's also the question of how much time must pass or how much analysis must an implementation be subjected to before we can start taking it "as given" that it is no longer weak. I view this in a very binary fashion: You either care about being post-quantum secure or you don't. If you do, using both cryptosystems will either result in something that is either strongly resistant to cryptanalysis by quantum computer or is no less secure than the non-QSE cryptosystem. Either way, you're no worse off.
aruss 11y ago
This is an exceedingly good article on the current state of theoretical crypto. I would have liked to see a little more on the new things that we can do with lattices - e.g. obfuscation or homomorphic encryption - because that's really what is motivating a lot of new research.
mtgx 11y ago
Is any of the lattice-based crypto faster than Bernstein and Peter Schwabe's code-based McBits? So far I've seen quite a few vulnerabilities for lattice-based crypto. They seem riddled with traps, so it could take a very long time before we are "sure" one is safe enough. http://binary.cr.yp.to/mcbits.html http://binary.cr.yp.to/mcbits.html
- aruss 11y ago
  One of the nice things about a lot of lattice-based crypto is that you can often just get certain homomorphic properties for free, which is why there's been a lot of recent interest in them.
- hannob 11y ago
  The problem with McBits is that it has really large keys. For a 128 bit security level you have one megabyte keys. That may be a reasonably conservative secure choice if you want post quantum cryptography today for certain applicatoins. But if you want to use it for something like TLS it's pretty much unusable. The lattice based systems look like they could be made to work in a real-world setting. The problem is of course that cryptographers will tell you that they aren't confident what works and what doesn't and what parameters are secure. And there are patents (both for ntru and parts of rlwe), which the article unfortunately doesn't mention. That's basically a dealbreaker for widespread use.
  - jeffreyrogers 11y ago
    What about https://en.wikipedia.org/wiki/Supersingular_Isogeny_Key_Exchange https://en.wikipedia.org/wiki/Supersingular_Isogeny_Key_Exch..., which seems to have reasonably small key sizes and fewer of the problems associated with lattices?

37 points by retupmoc01 11y ago

This stuff is all very interesting but, unless you're a researcher, has no immediate practical impact. What you would almost definitely accomplish by switching from (quantum cryptanalysis vulnerable) Curve25519 to a (supposed quantum safe) lattice or code-based algorithm is shipping something terribly insecure. It took a long time after the deployment of RSA, and an even longer time after ECC, to figure out the fiddly details of implementing it safely.

jackgavigan 11y ago
Why would you switch from one to t'other? Why not use both? That way, you get the best of both options that are available today.
- sp332 11y ago
  In terms of usability and compatibility, you get the worst of both worlds. And if we take it as given that current QSE implementations are weak, it's not going to add much security.
  - jackgavigan 11y ago
    In the context of PQ crypto, the primary objective is to implement a cryptosystem that is more resistant to cryptanalysis by quantum computer than a non-QSE algorithms like RSA. If that is indeed one's primary objective, usability and compatibility are far lesser concerns. We can't say for certain whether any cryptosystem will prove to be strong, particularly in the face of a theoretical/hypothetical technology like quantum computing, but it seems logical to assume that, until it is broken, there exists at least some possibility that it will turn out to be strong. There's also the question of how much time must pass or how much analysis must an implementation be subjected to before we can start taking it "as given" that it is no longer weak. I view this in a very binary fashion: You either care about being post-quantum secure or you don't. If you do, using both cryptosystems will either result in something that is either strongly resistant to cryptanalysis by quantum computer or is no less secure than the non-QSE cryptosystem. Either way, you're no worse off.

aruss 11y ago

This is an exceedingly good article on the current state of theoretical crypto. I would have liked to see a little more on the new things that we can do with lattices - e.g. obfuscation or homomorphic encryption - because that's really what is motivating a lot of new research.

mtgx 11y ago

Is any of the lattice-based crypto faster than Bernstein and Peter Schwabe's code-based McBits? So far I've seen quite a few vulnerabilities for lattice-based crypto. They seem riddled with traps, so it could take a very long time before we are "sure" one is safe enough. http://binary.cr.yp.to/mcbits.html http://binary.cr.yp.to/mcbits.html

aruss 11y ago
One of the nice things about a lot of lattice-based crypto is that you can often just get certain homomorphic properties for free, which is why there's been a lot of recent interest in them.
hannob 11y ago
The problem with McBits is that it has really large keys. For a 128 bit security level you have one megabyte keys. That may be a reasonably conservative secure choice if you want post quantum cryptography today for certain applicatoins. But if you want to use it for something like TLS it's pretty much unusable. The lattice based systems look like they could be made to work in a real-world setting. The problem is of course that cryptographers will tell you that they aren't confident what works and what doesn't and what parameters are secure. And there are patents (both for ntru and parts of rlwe), which the article unfortunately doesn't mention. That's basically a dealbreaker for widespread use.
- jeffreyrogers 11y ago
  What about https://en.wikipedia.org/wiki/Supersingular_Isogeny_Key_Exchange https://en.wikipedia.org/wiki/Supersingular_Isogeny_Key_Exch..., which seems to have reasonably small key sizes and fewer of the problems associated with lattices?