3 ms·

I asked a few years ago(I don't remember the specifics) what was the recommended post-quantum crypto, and basically the answer was that there wasn't any vetted

by im3w1l 6y ago

I asked a few years ago(I don't remember the specifics) what was the recommended post-quantum crypto, and basically the answer was that there wasn't any vetted and proven post-quantum crypto. So I don't think you can blame the industry here.

tialaramex 6y ago
There are some promising experiments. All of them are much worse than the algorithms we use today (including RSA) in practical terms, except that Shor's algorithm doesn't apply to them, and so they specifically fulfil the criterion of post-quantum public key crypto. [For symmetric encryption quantum computers would only matter if they were pretty fast/cheap and we didn't have ready-to-go 256-bit symmetric crypto, but we do] OpenSSH actually has an implementation of a reasonable contender for SSH. Google have experimented (in Chrome builds) with some of these contenders for TLS too. What you would likely want to do - since by definition these are relatively untried algorithms and so might be unsafe against adversaries with an existing not-at-all-quantum computer - is combine with an existing algorithm, most likely elliptic curve based, but RSA would be possible, under a "swiss cheese" model where you're only dead if an adversary penetrates all the layers. But like I said, much worse. Given that there aren't any suitably large quantum computers (and it's always possible that we'll eventually figure out we just can't build usefully large quantum computers, just like we eventually found out that while you can travel faster than sound you can't travel faster than light) it would make no sense to deploy this today, even though it continues to make sense to do research Just In Case.
- im3w1l 6y ago
  Wouldn't surprise me if there are classified quantum computers crunching numbers as we speak tbh.
  - AlexCoventry 6y ago
    I would be very surprised. That would involve keeping some huge leaps in basic research under wraps.
- Miraste 6y ago
  Could you expand on "much worse?" Are they slower, are they harder to implement?
  - rocqua 6y ago
    slower larger messages larger public keys larger private keys
  - marcosdumay 6y ago
    Just to expand the other answer you got. Slower, in a different complexity class from the classical ones (AKA O(n^2) instead of O(n), but I don't know what exact complexities the top candidates have right now, as a function of key length). Larger messages, in that a signature requires 100's or 10's of Mb instead of a few kb. Larger public keys, as again 100's of Mb instead of a few kb. Larger private keys, as in a few to 10's of Mb instead of 1/2 to a few kb. But I guess the most relevant "much worse" is that people have much less confidence that those algorithms are secure, and they are complex enough to hide huge traps that make implement RSA look like a walk in the park.
    - pezezin 6y ago
      You seem to be way outdated. A lot of work has been put on reducing key sizes. Dunno about signatures, but for key exchange SIKE (https://sike.org/ https://sike.org/) uses keys of a few hundred bytes, comparable in size to RSA.
      - tialaramex 6y ago
        Sure, SIKE is not so much bigger than existing approaches, but it is much slower than they are. Some of the other choices aren't so much slower but are far bigger, for example McEliece systems. There's lots of opportunities to make different trade-offs - at least if all of them survive a bit more scrutiny by smart motivated opponents - but they're all generally worse than what we have now - except that they resist Shor's algorithm.
        6y ago

by im3w1l 6y ago

tialaramex 6y ago

There are some promising experiments. All of them are much worse than the algorithms we use today (including RSA) in practical terms, except that Shor's algorithm doesn't apply to them, and so they specifically fulfil the criterion of post-quantum public key crypto. [For symmetric encryption quantum computers would only matter if they were pretty fast/cheap and we didn't have ready-to-go 256-bit symmetric crypto, but we do] OpenSSH actually has an implementation of a reasonable contender for SSH. Google have experimented (in Chrome builds) with some of these contenders for TLS too. What you would likely want to do - since by definition these are relatively untried algorithms and so might be unsafe against adversaries with an existing not-at-all-quantum computer - is combine with an existing algorithm, most likely elliptic curve based, but RSA would be possible, under a "swiss cheese" model where you're only dead if an adversary penetrates all the layers. But like I said, much worse. Given that there aren't any suitably large quantum computers (and it's always possible that we'll eventually figure out we just can't build usefully large quantum computers, just like we eventually found out that while you can travel faster than sound you can't travel faster than light) it would make no sense to deploy this today, even though it continues to make sense to do research Just In Case.

im3w1l 6y ago
Wouldn't surprise me if there are classified quantum computers crunching numbers as we speak tbh.
- AlexCoventry 6y ago
  I would be very surprised. That would involve keeping some huge leaps in basic research under wraps.
Miraste 6y ago
Could you expand on "much worse?" Are they slower, are they harder to implement?
- rocqua 6y ago
  slower larger messages larger public keys larger private keys
- marcosdumay 6y ago
  Just to expand the other answer you got. Slower, in a different complexity class from the classical ones (AKA O(n^2) instead of O(n), but I don't know what exact complexities the top candidates have right now, as a function of key length). Larger messages, in that a signature requires 100's or 10's of Mb instead of a few kb. Larger public keys, as again 100's of Mb instead of a few kb. Larger private keys, as in a few to 10's of Mb instead of 1/2 to a few kb. But I guess the most relevant "much worse" is that people have much less confidence that those algorithms are secure, and they are complex enough to hide huge traps that make implement RSA look like a walk in the park.
  - pezezin 6y ago
    You seem to be way outdated. A lot of work has been put on reducing key sizes. Dunno about signatures, but for key exchange SIKE (https://sike.org/ https://sike.org/) uses keys of a few hundred bytes, comparable in size to RSA.
    - tialaramex 6y ago
      Sure, SIKE is not so much bigger than existing approaches, but it is much slower than they are. Some of the other choices aren't so much slower but are far bigger, for example McEliece systems. There's lots of opportunities to make different trade-offs - at least if all of them survive a bit more scrutiny by smart motivated opponents - but they're all generally worse than what we have now - except that they resist Shor's algorithm.
      - 6y ago