Further Improvements of the Estimation of Key Enumeration with Applications to Solving LWE

Alessandro Budroni; Erik Mårtensson

Paper 2023/1547

Further Improvements of the Estimation of Key Enumeration with Applications to Solving LWE

Alessandro Budroni

, Technology Innovation Institute

Erik Mårtensson

, University of Bergen, Lund University

Abstract

In post-quantum cryptography, Learning With Errors (LWE) is one of the dominant underlying mathematical problems. The dual attack is one of the main strategies for solving the LWE problem, and it has recently gathered significant attention within the research community. The attack strategy consists of a lattice reduction part and a distinguishing part. The latter includes an enumeration subroutine over a certain number of positions of the secret key. Our contribution consists of giving a precise and efficient approach for calculating the expected complexity of such an enumeration procedure, which was missing in the literature. This allows us to decrease the estimated cost of the whole dual attack, both classically and quantumly, on well-known protocols such as Kyber, Saber, and TFHE. In addition, we explore different enumeration strategies to investigate some potential further improvements. As our method of calculating the expected cost of enumeration is pretty general, it might be of independent interest in other areas of cryptanalysis or even in different research areas.

Note: This is the version of the paper sent to "Cryptography and Communications", where it will soon be published. It is an extention of the paper "Improved Estimation of Key Enumeration with Applications to Solving LWE", which was presented as ISIT 2023 and is available on ePrint as 2023/139.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. Cryptography and Communications (CCDS)
DOI: https://doi.org/10.1007/s12095-024-00722-1
Keywords: Cryptography Lattice-based cryptography Learning with Errors Dual attacks.
Contact author(s): alessandro budroni @ tii ae
erik martensson @ eit lth se
History: 2024-06-07: last of 2 revisions; 2023-10-09: received; See all versions
Short URL: https://ia.cr/2023/1547
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1547,
      author = {Alessandro Budroni and Erik Mårtensson},
      title = {Further Improvements of the Estimation of Key Enumeration with Applications to Solving {LWE}},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1547},
      year = {2023},
      doi = {https://doi.org/10.1007/s12095-024-00722-1},
      note = {\url{https://eprint.iacr.org/2023/1547}},
      url = {https://eprint.iacr.org/2023/1547}
}