4 ms·

It seems that's exactly what the community is doing. Cloudflare recently enabled post-quantum cryptography, in which they're using X25519+Kyber [0]. Similarly,

It seems that's exactly what the community is doing. Cloudflare recently enabled post-quantum cryptography, in which they're using X25519+Kyber [0]. Similarly, Signal's post-quantum cryptography also uses the same [1]. I'm guessing this spawned from the fact that a post-quantum algorithm was broken on classical computers a few years ago [2]. So now any attacker would have to break both the classical algorithm and the post-quantum algorithm. [0] https://blog.cloudflare.com/post-quantum-to-origins/ https://blog.cloudflare.com/post-quantum-to-origins/ [1] https://signal.org/blog/pqxdh/ https://signal.org/blog/pqxdh/ [2] https://www.quantamagazine.org/post-quantum-cryptography-scheme-is-cracked-on-a-laptop-20220824/ https://www.quantamagazine.org/post-quantum-cryptography-sch...

cbeach 3y ago
I've probably missed an important detail here, but if the post-quantum algo can be broken on classical computers, what use is it, vs. a combination of classical and quantum computers?
- hannob 3y ago
  The algorithm that was broken is of course no longer used. The point is: Many of these algorithms are rather new. The fact that multiple post quantum algorithms have been broken that were seen as promising shows that there is a risk with these new algorithms. However, it should be said that the broken algorithms were in, let's say, more experimental subfields of post quantum cryptography.
- insanitybit 3y ago
  At this point quantum computers aren't breaking anything. Adding protections against them is nice because we're theoretically safe in the future. We don't want to compromise our safety now by choosing algorithms that are less battle tested though, so it's best to layer them. If it turns out that both the classical and quantum hard algorithms are weak we're just screwed, yes. That said, at this point it's not even clear, as far as I know, that many classical algorithms are event going to be broken under QC.
  - archgoon 3y ago
    [dead]
  - mthiim 3y ago
    Agreed. While manufacturers do show an impressive increase in the number of noisy qubits, we still have yet to see a demonstration of quantum error correction at anywhere near the levels needed to pull of a QC that breaks e.g. RSA.
    - insanitybit 3y ago
      It's also unclear (to me, perhaps not to others!) if the conversion from O(2^n) -> O(2^n/2) means it will be faster in practice on quantum hardware. https://eprint.iacr.org/2017/811 https://eprint.iacr.org/2017/811 > Reassessing Grover's Algorithm The proposal of this paper is that Grover's does not mean we need to double the size of symmetric keys to account for QM but that just a few extra bits are enough to prevent it from being efficient. Of course, there may be new QM algorithms that don't suffer and, again, it's best to start preparing now and not later. But I think it's noteworthy for the discussion about quantum preparedness.
      - mthiim 3y ago
        This conversion O(2^n) -> O(2^n/2) only applies to Grover's algorithm which can be used to break symmetric crypto (AES etc.). This is not the usual concern in the context of quantum computers because it just corresponds to halving the key space (in bits) which you can protect against by doubling the key size. So use AES-256 instead of AES-128. And the benefit by Grovers can only be had once. And as the paper you link to point out, maybe even that benefit is in question. However, the main concern with quantum computers vs cryptography is Shor's algorithm which works on RSA and ECC. Shor's has the potential to take the problem from exponential (or at least close to exponential but sub, in the case of RSA) to polynomial O(n^3) which is much more powerful (essentially taking a log of the running time!). That is still assuming, of course, that workable quantum computers of required since will appear and that all the associated problems with that (noisy qbits etc.) are solved. Other challenges could also show up (difficulties scaling for longer computations, more passes through quantum gates, larger super-positions or even that the quantum laws governing e.g. probability amplitudes don't hold with full accuracy at such scales).
- aardvarkr 3y ago
  It was “a” post quantum proposed algorithm, not “the” post quantum algo. Don’t judge an entire field because of one proposal that didn’t work.
- mratsim 3y ago
  It was broken because of a mathematical breakthrough using theory lurking in the dark corners of math. The protocol itself was also using some somewhat dark corner of math. Which is why having as many eyes as possible is important. Now it's very well possible that it comes back with mitigations. And even the still OK candidates are using a young area of math.
- tptacek 3y ago
  Secure transports are built out of asymmetric key agreement and symmetric bulk encryption, glued together with symmetric hashes. The symmetric cryptography isn't meaningfully threatened by any QC we're yet aware of. Hybrid PQC/classical schemes do two key agreements (an ECC kex and a LWE kem), and then plug both results into HKDF (conceptually: a symmetric hash) to derive a shared secret. In that scheme, you have to compromise both the PQC and ECC key agreements, independently.
- mthiim 3y ago
  That algorithm was never chosen as a final candidate, unlike Dilithium and Kyber. Nevertheless, it remains intriguing because it advanced significantly in the competition until this vulnerability was identified, which allows for it to be cracked in just a few minutes on a standard computer. This underscores the inherent risk of rapidly introducing new algorithms, whether quantum or not. While RSA might become vulnerable to future quantum computers, its resilience since its public introduction in 1977 (aside from the need to increase key sizes) is quite an achievement. This is why new algorithms should always be paired with trusted classical algorithms to get the best of both worlds: if the new post-quantum component is flawed, at least you're not worse off than if you had used classical algorithms. On the other hand, if quantum computers capable of breaking practical sizes of RSA or ECC emerge, there's still the hope that the post-quantum element remains intact.
  - forgotpwd16 3y ago
    Isn't it possible to decouple the two components, that is break the post-quantum one on classical computer and the classical one on a quantum computer, essentially making this combination null?
    - mthiim 3y ago
      Yes absolutely: If both security elements fail (quantum computers that break classical crypto appear, and the supposed post-quantum element turns out to be insecure as well) then you're screwed. By combining you get a chain is as strong as the strongest link - but not stronger! The motivation with combining is to avoid a scenario where you start using a new post-quantum algorithm which turns out to be really insecure (like happened to SPHINCS+) so you're actually worse off.

cbeach 3y ago

I've probably missed an important detail here, but if the post-quantum algo can be broken on classical computers, what use is it, vs. a combination of classical and quantum computers?

hannob 3y ago
The algorithm that was broken is of course no longer used. The point is: Many of these algorithms are rather new. The fact that multiple post quantum algorithms have been broken that were seen as promising shows that there is a risk with these new algorithms. However, it should be said that the broken algorithms were in, let's say, more experimental subfields of post quantum cryptography.
insanitybit 3y ago
At this point quantum computers aren't breaking anything. Adding protections against them is nice because we're theoretically safe in the future. We don't want to compromise our safety now by choosing algorithms that are less battle tested though, so it's best to layer them. If it turns out that both the classical and quantum hard algorithms are weak we're just screwed, yes. That said, at this point it's not even clear, as far as I know, that many classical algorithms are event going to be broken under QC.
- archgoon 3y ago
  [dead]
- mthiim 3y ago
  Agreed. While manufacturers do show an impressive increase in the number of noisy qubits, we still have yet to see a demonstration of quantum error correction at anywhere near the levels needed to pull of a QC that breaks e.g. RSA.
  - insanitybit 3y ago
    It's also unclear (to me, perhaps not to others!) if the conversion from O(2^n) -> O(2^n/2) means it will be faster in practice on quantum hardware. https://eprint.iacr.org/2017/811 https://eprint.iacr.org/2017/811 > Reassessing Grover's Algorithm The proposal of this paper is that Grover's does not mean we need to double the size of symmetric keys to account for QM but that just a few extra bits are enough to prevent it from being efficient. Of course, there may be new QM algorithms that don't suffer and, again, it's best to start preparing now and not later. But I think it's noteworthy for the discussion about quantum preparedness.
    - mthiim 3y ago
      This conversion O(2^n) -> O(2^n/2) only applies to Grover's algorithm which can be used to break symmetric crypto (AES etc.). This is not the usual concern in the context of quantum computers because it just corresponds to halving the key space (in bits) which you can protect against by doubling the key size. So use AES-256 instead of AES-128. And the benefit by Grovers can only be had once. And as the paper you link to point out, maybe even that benefit is in question. However, the main concern with quantum computers vs cryptography is Shor's algorithm which works on RSA and ECC. Shor's has the potential to take the problem from exponential (or at least close to exponential but sub, in the case of RSA) to polynomial O(n^3) which is much more powerful (essentially taking a log of the running time!). That is still assuming, of course, that workable quantum computers of required since will appear and that all the associated problems with that (noisy qbits etc.) are solved. Other challenges could also show up (difficulties scaling for longer computations, more passes through quantum gates, larger super-positions or even that the quantum laws governing e.g. probability amplitudes don't hold with full accuracy at such scales).
aardvarkr 3y ago
It was “a” post quantum proposed algorithm, not “the” post quantum algo. Don’t judge an entire field because of one proposal that didn’t work.
mratsim 3y ago
It was broken because of a mathematical breakthrough using theory lurking in the dark corners of math. The protocol itself was also using some somewhat dark corner of math. Which is why having as many eyes as possible is important. Now it's very well possible that it comes back with mitigations. And even the still OK candidates are using a young area of math.
tptacek 3y ago
Secure transports are built out of asymmetric key agreement and symmetric bulk encryption, glued together with symmetric hashes. The symmetric cryptography isn't meaningfully threatened by any QC we're yet aware of. Hybrid PQC/classical schemes do two key agreements (an ECC kex and a LWE kem), and then plug both results into HKDF (conceptually: a symmetric hash) to derive a shared secret. In that scheme, you have to compromise both the PQC and ECC key agreements, independently.
mthiim 3y ago
That algorithm was never chosen as a final candidate, unlike Dilithium and Kyber. Nevertheless, it remains intriguing because it advanced significantly in the competition until this vulnerability was identified, which allows for it to be cracked in just a few minutes on a standard computer. This underscores the inherent risk of rapidly introducing new algorithms, whether quantum or not. While RSA might become vulnerable to future quantum computers, its resilience since its public introduction in 1977 (aside from the need to increase key sizes) is quite an achievement. This is why new algorithms should always be paired with trusted classical algorithms to get the best of both worlds: if the new post-quantum component is flawed, at least you're not worse off than if you had used classical algorithms. On the other hand, if quantum computers capable of breaking practical sizes of RSA or ECC emerge, there's still the hope that the post-quantum element remains intact.
- forgotpwd16 3y ago
  Isn't it possible to decouple the two components, that is break the post-quantum one on classical computer and the classical one on a quantum computer, essentially making this combination null?
  - mthiim 3y ago
    Yes absolutely: If both security elements fail (quantum computers that break classical crypto appear, and the supposed post-quantum element turns out to be insecure as well) then you're screwed. By combining you get a chain is as strong as the strongest link - but not stronger! The motivation with combining is to avoid a scenario where you start using a new post-quantum algorithm which turns out to be really insecure (like happened to SPHINCS+) so you're actually worse off.