Paper 2023/139

Improved Estimation of Key Enumeration with Applications to Solving LWE

Alessandro Budroni, Technology Innovation Institute
Erik Mårtensson, Lund University, University of Bergen
Abstract

In post-quantum cryptography (PQC), Learning With Errors (LWE) is one of the dominant underlying mathematical problems. For example, in NIST's PQC standardization process, the Key Encapsulation Mechanism (KEM) protocol chosen for standardization was Kyber, an LWE-based scheme. Recently the dual attack surpassed the primal attack in terms of concrete complexity for solving the underlying LWE problem for multiple cryptographic schemes, including Kyber. The dual attack consists of a reduction part and a distinguishing part. When estimating the cost of the distinguishing part, one has to estimate the expected cost of enumerating over a certain number of positions of the secret key. Our contribution consists of giving a polynomial-time approach for calculating the expected complexity of such an enumeration procedure. This allows us to revise the complexity of the dual attack on the LWE-based protocols Kyber, Saber and TFHE. For all these schemes we improve upon the total bit-complexity in both the classical and the quantum setting. As our method of calculating the expected cost of enumeration is fairly general, it might be of independent interest in other areas of cryptography or even in other research areas.

Note: Revised version.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
EnumerationLWELattice-based CryptographyDual Attack
Contact author(s)
budroni alessandro @ gmail com
erik martensson @ uib no
History
2023-05-11: revised
2023-02-06: received
See all versions
Short URL
https://ia.cr/2023/139
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/139,
      author = {Alessandro Budroni and Erik Mårtensson},
      title = {Improved Estimation of Key Enumeration with Applications to Solving LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2023/139},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/139}},
      url = {https://eprint.iacr.org/2023/139}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.