Thank you, Bas! And to save time for those who don’t want to follow the NIST mailing list trail – here’s the response from Leo Ducas posted there:
Dear All, Thank you, Kevin, Charles, Yixin, Jean-Pierre for your careful analysis and report. While most of the points below are acknowledged in your paper, I would like to highlight the specific cost modeling points that deserve further consideration, to contextualize the numbers you advertised, and invite further work: A/ As noted on footnote 6, the current estimate uses a GSA slope for the output of BKZ, but use a progressive-BKZ costing, undercosting lattice reduction by 2.5 bits [1] B/ These estimations do not include overheads documented in [2], of about 5 bits at security level 1. C/ The costs C_add=160 and C_mult=1024 are questionable, given that one runs an FFT on more than 2^100 scalars. These costs suggest a calculation at 32 bits of precisions, which may lead to numerical error beyond the precision required to detect the solution among the so many candidates. It should be noted that item B/ applies to both primal and dual attacks: the current best estimate for the primal attack [3] also doesn't include that overhead. Item A/ and C/ are specific to the current analysis of dual attacks. With A/ and C/ in mind, it seems that the primal and dual attacks are neck-to-neck, and therefore agree with your conclusion that the dual attack should not be dismissed. With B/ in mind, there remains a few bits to be gained by cryptanalysts before the security levels would be convincingly crossed. [1] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s/m/BZFRC8hiAAAJ <_blank> [2] https://eprint.iacr.org/2022/922 <_blank> Estimating the Hidden Overheads in the BDGL Lattice Sieving Algorithm Léo Ducas [3] https://eprint.iacr.org/2024/067 <_blank> A Refined Hardness Estimation of LWE in Two-step Mode Wenwen Xia, Leizhang Wang, Geng Wang, Dawu Gu, Baocang Wang -- Léo -- V/R, Uri From: Bas Westerbaan <bas=40cloudflare....@dmarc.ietf.org> Date: Tuesday, April 15, 2025 at 06:04 To: tls@ietf.org <tls@ietf.org> Subject: [EXT] [TLS] Re: Boring cryptography, and the opposite extreme For everyone's convenience: https: //groups. google. com/a/list. nist. gov/g/pqc-forum/c/RsQbm_AQfzs/m/19o76lsyCwAJ On Tue, Apr 15, 2025 at 11: 55 AM D. J. Bernstein <djb@ cr. yp. to> wrote: A message has just appeared on pqc-forum claiming ZjQcmQRYFpfptBannerStart This Message Is From an External Sender This message came from outside the Laboratory. ZjQcmQRYFpfptBannerEnd For everyone's convenience: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/RsQbm_AQfzs/m/19o76lsyCwAJ <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/RsQbm_AQfzs/m/19o76lsyCwAJ> On Tue, Apr 15, 2025 at 11:55 AM D. J. Bernstein <d...@cr.yp.to <mailto:d...@cr.yp.to>> wrote: A message has just appeared on pqc-forum claiming yet another attack improvement against lattices---improving what are called "dual" attacks and breaking earlier claims about those attacks not working; concretely, reducing "the security of Kyber-512/768/1024 by approximately 3.5/11.9/12.3 bits" below Kyber's security goals in the same cost model used in the round-3 Kyber submission. For comparison, the round-3 Kyber security analysis had claimed that "primal" attacks for round-3 Kyber-512 (after patches to Kyber-512 in response to earlier security issues) were ~10 bits above the goals, and that dual attacks were "significantly more expensive" than that. The "significantly" slowdown wasn't quantified, so the reader is left not even knowing how much improvement there has been. Did these 5 years of public attack development reduce the costs of Kyber-512 dual attacks by 20 bits? 30 bits? As for the future, how much farther will the cliff crumble? We don't know. Continued excitement for researchers! Lattice attacks today are far less stable than ECC attacks were two decades ago. To be clear, I'm not opposing efforts to roll out post-quantum systems: on the contrary, we have to _try_ to stop quantum attacks. I'm simply saying that we shouldn't be ripping out seatbelts. ---D. J. Bernstein _______________________________________________ TLS mailing list -- tls@ietf.org <mailto:tls@ietf.org> To unsubscribe send an email to tls-le...@ietf.org <mailto:tls-le...@ietf.org>
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ TLS mailing list -- tls@ietf.org To unsubscribe send an email to tls-le...@ietf.org
