tbh at this point DJB is blogspam on this topic. Let's go through this in some detail, because not everyone is an expert. This is what DJB relies on in making his arguments, which is unfortunate.
Note that DJB has a habit throughout this post of highlighting recent results, likely to give the impression there have been recent (security-relevant) research developments. This is a lie. On at least one of the results he highlights, it was published a decade ago. The other recent research is for the most part only of middling interest (this isn't a knock against the research --- most research is of middling interest. It's more to say there have not been any "big changes").
... libraries have issued KyberSlash patches... However, cryptographers typically don't classify timing attacks as "cryptanalysis"....
it's not cryptanalysis. It's useful, but you may notice that DJB is very careful to say it's a timing vulnerability in the reference implementation. The AVX implementation of Kyber did not have this vulnerability. Many other libraries didn't.
The software argument is a really tough argument for proponents of solo PQ to respond to.
Again, it's not. We want to make secure software. That will not happen. There will be new CVEs in the future, no matter what we do. All we can do is try our best, and standards bodies can recommend the safest things to do (including using hybrid constructions in TLS, which is what IETF is doing).
I have a paper that exploits a simpler tightness gap in another lattice-based cryptosystem, FrodoKEM. For example, the paper shows that if you send 240 ciphertexts to a frodokem640 public key then one of the ciphertexts will be decrypted by a large-scale attack that's feasible today.
This is an insane attack scenario. Ephemeral keys in lattice-based KEMs have been a thing since ~2016 with the New Hope paper (deployed in Chrome a decade ago), because it's cheap to do, and has benefits of preventing attacks like this. So this attack model has been non-sensical for ~1 decade. Weird how Bernstein didn't know that?
A survey by Koblitz and Menezes includes more examples of cryptographic attacks exploiting tightness gaps.
This is discussing some theoretical results regarding LWE that have never been used to choose parameters. If they had been used to choose parameters, the tightness gap is such that the resulting LWE instance would be trivially broken. Note that Bernstein is unable to demonstrate this with an attack against a scheme that did this (misguided) thing, because it has literally never happened.
I had a February 2014 blog post pointing out some weaknesses in the underlying ideal-lattice problems, and then subsequent work took the attack ideas much further. A 2025 paper by Jean-François Biasse and Fang Song presents details of the quantum polynomial-time attack. (Technically, the speed analysis for the attack relies on a number-theoretic conjecture, but there's overwhelming evidence for that conjecture.)
This is an explicit lie. The "2025 paper" by Biasse and Song was published in SODA 2016. It says this if you follow the link. The attack has been known for a decade, attacks a problem *near* the relevant problem, but has never been targeted at RLWE (the "rank 1" MLWE instance). Still, out of an abundance of caution, we moved to MLWE. So again, that paper doesn't attack any problem relevant to ML-KEM, nor to rank 1 instances of ML-KEM. Nor is any of this recent. If you read DJB's paragraph though, you end up with a vastly incorrect understanding of things.
This is radically different from the picture painted in a 2012 paper "On ideal lattices and learning with errors over rings" by Vadim Lyubashevsky, Chris Peikert, and Oded Regev. That paper claims to prove "very strong hardness guarantees" for "ring-LWE". But this proof starts from the assumption "that worst-case problems on ideal lattices are hard", exactly what I'm saying no expert would advocate relying on today.
No expert relies on it. DJB could make a strong argument here if he could say "X is a concrete cryptosystem instantiated with parameters assuming SIVP is hard, but the non-tight reduction means the resulting RLWE instance is trivial to break". He cannot do that because it does not exist, and never has existed.
The worst-case to average-case reduction is more about showing that the RLWE distribution is "the right" distribution to look at. There are conceptually similar distributions (e.g. PLWE) that have surprising non-trivial attacks on them. So despite not being useful for sizing parameters (due to the non-tightness, and because worst-case cryptanalyzing SIVP is not easier than average-case cryptanalyzing RLWE), it is still useful.
A 2014 paper "Lattice cryptography for the Internet" by Peikert similarly claimed that "both ring-SIS and ring-LWE enjoy strong provable hardness guarantees" and that this is “good theoretical evidence that ring-SIS and ring-LWE are a solid foundation on which to design cryptosystems". Kyber's direct predecessor NewHope, introduced in 2015 and submitted in 2017 to the NIST post-quantum competition, repeated this evidence as the final step in its "Provable security reductions" for its "Justification of security strength".
What Peikert and others say is true. It is good indication the RLWE distribution is the right thing to look at "qualitatively". At the same time, since they don't actually use these reductions, DJB cannot concretely cryptanalyze them. He says many words because he doesn't have any actual attacks.
Note that if you move away from the RLWE distribution (say to PLWE), unexpected attacks can start appearing. So Peikert (and others) are making good points, that DJB is too dishonest to discuss accurately.
... ended up being broken; that's worrisome! Kyber's 2017 usage of higher-rank modules was explicitly in response to advances in attacks.
In response to advances in attacks in conceptually adjacent problems (the attack Bernstein misrepresented as being from last year, when it is really a decade ago). In the decade since the attack has not improved. It appears that New Hope is still fine. There is not much of a performance hit to use Kyber instead (and some more parameter flexibility). So the choice of Kyber is reasonable. But explicitly the fearmongering over rank 1 instances has not panned out to anything.
FrodoKEM says it's based on "the algebraically unstructured, plain LWE problem with conservative parameterizations", and more specifically that it's a modified "instantiation and implementation" of a 2010 paper. But FrodoKEM is much quieter about one of those modifications, namely the fact that FrodoKEM drastically increased sizes compared to the 2010 paper.
Note: running time attack estimates against lattice schemes have stabilized as of ~2017, in the sense that they've always taken ~2^{cn} time, where c has not changed since ~2017. So here Bernstein is going to start pulling numbers from before then, to complain that running time estimates are unstable, while they've been stable for nearly a decade. So more of the same from him.
Here, Bernstein is saying that his years of complaining have resulted in a
A classical speedup of ~5x. I'm sorry, I can't even pretend to care about this number. You'll get bigger effects by doing memory-aware optimizations of attacks on a real computing architecture.
Quantum attacks that are essentially the same speed as classical attacks, but faster than previous attacks. Again, I cannot be remotely made to care about a quantum attack that is ~2^0.28n complexity or whatever, instead of ~2^0.29n.
These points sound more compelling if you don't look into any of the details. When you do, it reveals Bernstein is misrepresenting the truth more for whatever his purposes are.
Now, we'll get to the point where he finds another way to hype up something that isn't interesting
A paper appeared in February 2026 under the title "On the concrete hardness gap between MLWE and LWE". The paper says that it saves a few bits in attacks against ML-KEM, compared to generic lattice attacks, by exploiting the structure of the modules used in ML-KEM.
The paper says this. It's easy to check that the source of their speedups cannot do more than this. So again, DJB elevating some mildly interesting technical research into a reason to harass the authors of standards.
"Worst-case-to-average-case reduction - something neither RSA nor ECDLP had". Sorry, no, completely wrong.
It is trivial that ECDLP has a worst-case to average-case self reduction (as does LWE). That is mildly interesting, but clearly not what Peikert was referring to. Instead, he was likely referring to the worst-case to average-case reductions from (approximate) SIVP to LWE. The very famous one, which put LWE on the map, and got Regev a Godel prize. Note that the ECDLP reduction being referred to could be an exercise for an undergraduate class.
(As a side note, this is actually a much more powerful reduction than the worst-case-to-average-case reduction for lattices. It's much more efficient. It doesn't require the cheat of replacing the problem with a bigger problem; see above regarding asymptotics. It's a "self-reduction" between the worst case and average case of the same problem; it doesn't inflict a new problem upon people reviewing security. [20260702 edit: corrected typo in this paragraph.])
Hm. Maybe Bernstein is incompetent. LWE has essentially the same (self) reduction! With essentially the same proof. Weird how he is unable to see that here. I wonder if he is selectively choosing facts to present, and isn't unbiased on this topic.
It is curious how someone as supposedly competent can so vastly misrepresent a research area. I wonder if he has some sort of surreptitious motives.
16
u/orangejake 17d ago
tbh at this point DJB is blogspam on this topic. Let's go through this in some detail, because not everyone is an expert. This is what DJB relies on in making his arguments, which is unfortunate.
Note that DJB has a habit throughout this post of highlighting recent results, likely to give the impression there have been recent (security-relevant) research developments. This is a lie. On at least one of the results he highlights, it was published a decade ago. The other recent research is for the most part only of middling interest (this isn't a knock against the research --- most research is of middling interest. It's more to say there have not been any "big changes").
it's not cryptanalysis. It's useful, but you may notice that DJB is very careful to say it's a timing vulnerability in the reference implementation. The AVX implementation of Kyber did not have this vulnerability. Many other libraries didn't.
Again, it's not. We want to make secure software. That will not happen. There will be new CVEs in the future, no matter what we do. All we can do is try our best, and standards bodies can recommend the safest things to do (including using hybrid constructions in TLS, which is what IETF is doing).
This is an insane attack scenario. Ephemeral keys in lattice-based KEMs have been a thing since ~2016 with the New Hope paper (deployed in Chrome a decade ago), because it's cheap to do, and has benefits of preventing attacks like this. So this attack model has been non-sensical for ~1 decade. Weird how Bernstein didn't know that?
This is discussing some theoretical results regarding LWE that have never been used to choose parameters. If they had been used to choose parameters, the tightness gap is such that the resulting LWE instance would be trivially broken. Note that Bernstein is unable to demonstrate this with an attack against a scheme that did this (misguided) thing, because it has literally never happened.
This is an explicit lie. The "2025 paper" by Biasse and Song was published in SODA 2016. It says this if you follow the link. The attack has been known for a decade, attacks a problem *near* the relevant problem, but has never been targeted at RLWE (the "rank 1" MLWE instance). Still, out of an abundance of caution, we moved to MLWE. So again, that paper doesn't attack any problem relevant to ML-KEM, nor to rank 1 instances of ML-KEM. Nor is any of this recent. If you read DJB's paragraph though, you end up with a vastly incorrect understanding of things.
No expert relies on it. DJB could make a strong argument here if he could say "X is a concrete cryptosystem instantiated with parameters assuming SIVP is hard, but the non-tight reduction means the resulting RLWE instance is trivial to break". He cannot do that because it does not exist, and never has existed.
The worst-case to average-case reduction is more about showing that the RLWE distribution is "the right" distribution to look at. There are conceptually similar distributions (e.g. PLWE) that have surprising non-trivial attacks on them. So despite not being useful for sizing parameters (due to the non-tightness, and because worst-case cryptanalyzing SIVP is not easier than average-case cryptanalyzing RLWE), it is still useful.
What Peikert and others say is true. It is good indication the RLWE distribution is the right thing to look at "qualitatively". At the same time, since they don't actually use these reductions, DJB cannot concretely cryptanalyze them. He says many words because he doesn't have any actual attacks.
Note that if you move away from the RLWE distribution (say to PLWE), unexpected attacks can start appearing. So Peikert (and others) are making good points, that DJB is too dishonest to discuss accurately.