[TLS] Re: [EXT] Re: Boring cryptography, and the opposite extreme

["Blumenthal, Uri - 0553 - MITLL" <[e-mail]>]

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=[e-mail]>
Date: Tuesday, April 15, 2025 at 06:04
To: [e-mail] <[e-mail]>
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 <[e-mail] <mailto:[e-mail]>> 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 -- [e-mail] <mailto:[e-mail]>
To unsubscribe send an email to [e-mail] <mailto:[e-mail]>