John Mattsson writes:
> NIST has typically used terms like "computational resources comparable
> to or greater"
NIST also said "floor". FIPS 203 then unambiguously stated "at least as
secure". So the wiggle room of "comparable" is gone.
What's more important is that, as I said, there's a huge fog of
uncertainties regarding the costs of known lattice attacks. As an
example of the scale of the uncertainties, the final (2021) Kyber team
document
https://web.archive.org/web/20230310174959/https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf
said that, because of "known unknowns", the Kyber-512 attack cost could
be anywhere between 2^135 bit operations and 2^165 bit operations. (It
also claimed that the security was "well-studied".)
Research since then has pinned down some of those "known unknowns" but
identified even more, while also producing >10 bits of clear speedups.
Putting together a combined analysis covering all of the latest "known
unknowns" would be a lot of work (and would be obsolete as soon as the
next advance appears), but I wouldn't be surprised by something around
2^110 on the low end and something around 2^150 on the high end. The
AES-128 target is slightly above 2^140.
The Crypto 2025 paper takes a point estimate, concluding that it beats
the AES-128 target. This could certainly be correct, but could also be
wrong given the uncertainties. In the opposite direction, the FIPS 203
security claim could be correct but also can't be justified today.
> "highly unlikely that the known sources of uncertainty are large
> enough to make Kyber512 signifcantly less secure than AES128" [1-2].
FIPS 203 does not say "unlikely" and does not say "significantly less".
It says "at least as secure".
Regarding the details, one point NIST made was that there was an error
in an earlier dual-attack paper. But that's what has now been fixed by
the Crypto 2025 paper, with a clever new optimization that also allows
a much more convincing analysis.
Meanwhile there are many other errors in lattice papers, but for some
reason there's much more advertising of the errors that make lattices
sound safe than of the errors in the opposite direction. It's deeply
problematic that the uncertainties and errors end up obscuring how much
better the attacks are getting.
> Ragarding 2022/1750, there has already been a lengthy discussion on
> PQC forum, where you accused NIST of being stupid and not being able
> to count [3].
That wasn't regarding 2022/1750. But, yes, NIST did make a _really_
serious counting mistake: multiplying the "real cost of memory access"
by the total number of bit operations in an attack, rather than merely
by the number of memory accesses in the attack. I have three blog posts
regarding this calculation error:
https://blog.cr.yp.to/20231003-countcorrectly.html
https://blog.cr.yp.to/20231023-clumping.html
https://blog.cr.yp.to/20231125-kyber.html
The first blog post also summarized the "research that would be needed
for a correct calculation". Two papers then did that research,
concluding asymptotically and concretely that memory access---when
counted correctly and properly optimized---adds essentially nothing to
the attack costs:
https://eprint.iacr.org/2024/080
https://eprint.iacr.org/2024/739
So NIST's calculations _and_ conclusions have been debunked at this
point.
> The majority of PQC forum agreed with NIST.
That's neither correct nor relevant. The calculations have been
debunked, and NIST is ethically obliged to issue a retraction.
> The only thing that should be withdrawed are your personal attacks on
> the NIST cryptography team.
Saying that NIST botched a calculation is not a personal attack.
> The new de facto standard is X25519MLKEM768
It's not that simple. For example:
https://engineering.fb.com/2024/05/22/security/post-quantum-readiness-tls-pqr-meta/
The big picture is that there's a spread of uses of 512, 768, 1024, plus
of course NSA throwing a lot of money around to discourage hybrids.
---D. J. Bernstein
_______________________________________________
TLS mailing list -- tls@ietf.org
To unsubscribe send an email to tls-le...@ietf.org
