Here's a chart I sent CFRG a few weeks ago of recent claims regarding
the exponent, including memory-access costs, of attacks against the most
famous lattice problem, namely the "shortest-vector problem" (SVP):
* November 2023: 0.396, and then 0.349 after an erratum:
https://web.archive.org/web/20231125213807/https://finiterealities.net/kyber512/
* December 2023: 0.349, or 0.329 in 3 dimensions:
https://web.archive.org/web/20231219201240/https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/faq/Kyber-512-FAQ.pdf
* January 2024: 0.311, or 0.292 in 3 dimensions:
https://web.archive.org/web/20240119081025/https://eprint.iacr.org/2024/080.pdf
I then wrote: "Something is very seriously wrong when the asymptotic
security level claimed three months ago for SVP---as part of a chorus of
confident claims that these memory-access costs make Kyber-512 harder to
break than AES-128---is 27% higher than what's claimed today."
This sort of dramatic instability in security analyses is exciting for
cryptographers, and one of the perennial scientific attractions of
lattice-based cryptography. It's also a security risk. The right way to
handle this tension is to treat these cryptosystems _very_ carefully.
The wrong way is to try to conceal the instability.
John Mattsson writes:
> https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/faq/Kyber-512-FAQ.pdf
That's the December 2023 document above. There are many problems with
that document, but the most obvious is that the document claims a much
higher exponent for the "cost of memory access" than the January 2024
document. This is not some minor side issue: the December 2023 document
labels this cost as an "important consideration" and spends pages
computing the exponent.
One wonders why NIST didn't issue a prompt statement either admitting
error or disputing the January 2024 document. That document was posted
almost two full months ago. The document is on the list of accepted
papers for NIST's next workshop, but accepting a paper (1) isn't a
statement of endorsement and (2) doesn't tell readers "Please disregard
the fundamentally flawed December 2023 statement".
> https://keymaterial.net/2023/11/18/kyber512s-security-level/
See https://blog.cr.yp.to/20231125-kyber.html for comments on that.
---D. J. Bernstein
_______________________________________________
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls
