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.

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.

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.

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

> 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.

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).

Yeah, my point was more that there's a lot of "this QM version of the algorithm destroys that crypto scheme" when it may be a lot more nuanced. I used Grover's as an example of that - on its face Grover's implies that you need to double the key size to be safe but there's reason to believe that that's not true in practice. I assume that may be the case with Shor's as well.

The best thing to do is to layer them, as is standard.

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.

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.

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.

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.

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?

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.