3 ms·

It's not the same place because access to quantum computers is (and likely will be for a while) heavily asymmetric. People who want to break encryption will be

It's not the same place because access to quantum computers is (and likely will be for a while) heavily asymmetric. People who want to break encryption will be able to do so, while people who want unbreakable encryption will, except for the tiny overlap with the former set, not have access to the hardware.

iainmerrick 3y ago
I don’t think you need a quantum computer to do post-quantum encryption. It’s just an encryption method that’s believed not to have any quantum shortcuts.
- ghaff 3y ago
  Correct. At the moment seems to be mostly lattice-based approaches.
dmurray 3y ago
No, post-quantum cryptography is focused on methods where encryption can be done with classical computers. Post-quantum methods have other disadvantages, primarily that they haven't been studied as deeply as traditional methods (especially RSA) so they may be vulnerable to classes of attack we haven't thought of yet. https://en.m.wikipedia.org/wiki/Post-quantum_cryptography https://en.m.wikipedia.org/wiki/Post-quantum_cryptography
JoachimS 3y ago
AFAIK, this is basically the opposite of how it probably will pan out. Some organsations MAY someday have Quantum Computers capable of cracking some asymmetric keys (RSA). All of us will have access to cryptographic algorithms (inlcuding open source implementations) that can't be cracked by the Quantum Computers. These algorithms are executed on our normal, classical computers. We already have a first set of post quantum computer cryptographic algorithms. See the NIST competition for example. Their implementations still looks immature (some have fallen against classical attacks, including side channel issues). But we'll get there. We will also have to (yet again) deal with having algorithm agility, which adds complexity. Quantum Computers are not magical things. We can (and do) know type of problems, algorithms, operations they should be better than classical computers to solve (called quantum supremacy). Shor's algorithm, which provides exponential speedup of cracking RSA key is an example of such an algorithm. What we so far don't consider that much is the feasibility to perform these algorithms in reality. That is, we look at the asymptotic speedup, not the practical speedup. There is a really good paper by people from the MS PQ team that looked at this. Highly recommended: https://cacm.acm.org/magazines/2023/5/272276-disentangling-hype-from-practicality-on-realistically-achieving-quantum-advantage/fulltext https://cacm.acm.org/magazines/2023/5/272276-disentangling-h...
- vitus 3y ago
  Shor's algorithm also solves the discrete logarithm problem, so it also theoretically breaks Elliptic Curve Diffie-Hellman. That is, it breaks both of the main types of key-exchange algorithms (as well as SRP) in use today with TLS. (Not PSK, although that in turn isn't usable in a limited-trust environment like the broader internet.) My understanding is that any use of post-quantum crypto today is layered on top of existing crypto (so breaking one is insufficient to compromise the channel), in large part due to the relative immaturity of the field that you've mentioned. The threat model here is not necessarily that we expect anyone to have sufficiently capable quantum computers (and/or algorithmic breakthroughs) in the immediate future, but that a potential adversary might store some encrypted comms that they can later decrypt. Perfect forward secrecy doesn't protect you against an algorithmic break.

iainmerrick 3y ago

I don’t think you need a quantum computer to do post-quantum encryption. It’s just an encryption method that’s believed not to have any quantum shortcuts.

ghaff 3y ago
Correct. At the moment seems to be mostly lattice-based approaches.

dmurray 3y ago

No, post-quantum cryptography is focused on methods where encryption can be done with classical computers. Post-quantum methods have other disadvantages, primarily that they haven't been studied as deeply as traditional methods (especially RSA) so they may be vulnerable to classes of attack we haven't thought of yet. https://en.m.wikipedia.org/wiki/Post-quantum_cryptography https://en.m.wikipedia.org/wiki/Post-quantum_cryptography

JoachimS 3y ago

AFAIK, this is basically the opposite of how it probably will pan out. Some organsations MAY someday have Quantum Computers capable of cracking some asymmetric keys (RSA). All of us will have access to cryptographic algorithms (inlcuding open source implementations) that can't be cracked by the Quantum Computers. These algorithms are executed on our normal, classical computers. We already have a first set of post quantum computer cryptographic algorithms. See the NIST competition for example. Their implementations still looks immature (some have fallen against classical attacks, including side channel issues). But we'll get there. We will also have to (yet again) deal with having algorithm agility, which adds complexity. Quantum Computers are not magical things. We can (and do) know type of problems, algorithms, operations they should be better than classical computers to solve (called quantum supremacy). Shor's algorithm, which provides exponential speedup of cracking RSA key is an example of such an algorithm. What we so far don't consider that much is the feasibility to perform these algorithms in reality. That is, we look at the asymptotic speedup, not the practical speedup. There is a really good paper by people from the MS PQ team that looked at this. Highly recommended: https://cacm.acm.org/magazines/2023/5/272276-disentangling-hype-from-practicality-on-realistically-achieving-quantum-advantage/fulltext https://cacm.acm.org/magazines/2023/5/272276-disentangling-h...

vitus 3y ago
Shor's algorithm also solves the discrete logarithm problem, so it also theoretically breaks Elliptic Curve Diffie-Hellman. That is, it breaks both of the main types of key-exchange algorithms (as well as SRP) in use today with TLS. (Not PSK, although that in turn isn't usable in a limited-trust environment like the broader internet.) My understanding is that any use of post-quantum crypto today is layered on top of existing crypto (so breaking one is insufficient to compromise the channel), in large part due to the relative immaturity of the field that you've mentioned. The threat model here is not necessarily that we expect anyone to have sufficiently capable quantum computers (and/or algorithmic breakthroughs) in the immediate future, but that a potential adversary might store some encrypted comms that they can later decrypt. Perfect forward secrecy doesn't protect you against an algorithmic break.