Paper 2023/243

Memory-Efficient Attacks on Small LWE Keys

Andre Esser, Technology Innovation Institute
Rahul Girme, Indian Institute of Technology Madras
Arindam Mukherjee, Indian Institute of Technology Madras
Santanu Sarkar, Indian Institute of Technology Madras
Abstract

The LWE problem is one of the prime candidates for building the most efficient post-quantum secure public key cryptosystems. Many of those schemes, like Kyber, Dilithium or those belonging to the NTRU-family, such as NTRU-HPS, -HRSS, BLISS or GLP, make use of small max norm keys to enhance efficiency. The presumably best attack on these schemes is a hybrid attack, which combines combinatorial techniques and lattice reduction. While lattice reduction is not known to be able to exploit the small max norm choices, May recently showed (Crypto 2021) that such choices allow for more efficient combinatorial attacks. However, these combinatorial attacks suffer enormous memory requirements, which render them inefficient in realistic attack scenarios and, hence, make their general consideration when assessing security questionable. Therefore, more memory-efficient substitutes for these algorithms are needed. In this work, we provide new combinatorial algorithms for recovering small max norm LWE secrets using only a polynomial amount of memory. We provide analyses of our algorithms for secret key distributions of current NTRU, Kyber and Dilithium variants, showing that our new approach outperforms previous memory-efficient algorithms. For instance, considering uniformly random ternary secrets of length $n$ we improve the best known time complexity for polynomial memory algorithms from $2^{1.063n}$ down-to $2^{0.926n}$. We obtain even larger gains for LWE secrets in $\{-m,\ldots,m\}^n$ with $m=2,3$ as found in Kyber and Dilithium. For example, for uniformly random keys in $\{-2,\ldots,2\}^n$ as is the case for Dilithium we improve the previously best time from $2^{1.742n}$ down-to $2^{1.282n}$. Our fastest algorithm incorporates various different algorithmic techniques, but at its heart lies a nested collision search procedure inspired by the Nested-Rho technique from Dinur, Dunkelman, Keller and Shamir (Crypto 2016). Additionally, we heavily exploit the representation technique originally introduced in the subset sum context to make our nested approach efficient.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Keywords
Learning with Errorsnested collision searchrepresentation techniquepolynomial memory
Contact author(s)
andre r esser @ gmail com
rahulgirme3 @ gmail com
arindamaths @ gmail com
sarkar santanu bir1 @ gmail com
History
2023-11-08: revised
2023-02-21: received
See all versions
Short URL
https://ia.cr/2023/243
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/243,
      author = {Andre Esser and Rahul Girme and Arindam Mukherjee and Santanu Sarkar},
      title = {Memory-Efficient Attacks on Small LWE Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2023/243},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/243}},
      url = {https://eprint.iacr.org/2023/243}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.