Selected Algorithm 2022 OFFICIAL COMMENT: CRYSTALS-KYBER

[Kevin Carrier]

Dear All,

We would like to share a recent result: https://eprint.iacr.org/2022/1750 . In this work, we propose an improvement to the latest dual lattice attacks. While lattice-based dual attacks were strongly questioned by Ducas and Pulles at CRYPTO2023, where it was shown that the independence assumptions used in the analysis of the most recent dual attacks could not hold, the analysis of our attack on the contrary does not rely on these assumptions and is backed up by experimental evidence.

Our findings indicate that this advancement weakens the security claims of CRYSTALS-Kyber. Specifically, we estimate that our algorithm reduces the security of Kyber-512/768/1024 by approximately 3.5/11.9/12.3 bits, respectively, compared to the NIST recommendations, within the Nearest-Neighbor Cost model used in the Kyber submission. While our computational model is admittedly simplistic and the complexity estimates may be subject to refinement, our results indicate that dual attacks should not be dismissed in security assessments of lattice-based cryptosystems such as Kyber.

Best regards,

Kevin Carrier, Charles Meyer-Hilfiger, Yixin Shen, Jean-Pierre Tillich

[Leo Ducas]

Dear All,

Thank you Kevin, Charles, Yixin, Jean-Pierre for your careful analysis and report.

While most of the points below are aknowledged 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 use 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 questionnable, given that one runs an FFT on more than 2^100 scalars. These cost 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

[2] https://eprint.iacr.org/2022/922
Estimating the Hidden Overheads in the BDGL Lattice Sieving Algorithm
Léo Ducas

[3] https://eprint.iacr.org/2024/067
A Refined Hardness Estimation of LWE in Two-step Mode
Wenwen Xia, Leizhang Wang, Geng Wang, Dawu Gu, Baocang Wang

-- Léo