Paper 2023/1508

Provable Dual Attacks on Learning with Errors

Amaury Pouly, French National Centre for Scientific Research
Yixin Shen, King's College London

Learning with Errors (LWE) is an important problem for post-quantum cryptography (PQC) that underlines the security of several NIST PQC selected algorithms. Several recent papers have claimed improvements on the complexity of so-called dual attacks on LWE. These improvements make dual attacks comparable to or even better than primal attacks in certain parameter regimes. Unfortunately, those improvements rely on a number of untested and hard-to-test statistical assumptions. Furthermore, a recent paper claims that the whole premise of those improvements might be incorrect. The goal of this paper is to improve the situation by proving the correctness of a dual attack without relying on any statistical assumption. Although our attack is greatly simplified compared to the recent ones, it shares many important technical elements with those attacks and can serve as a basis for the analysis of more advanced attacks. We provide some rough estimates on the complexity of our simplified attack on Kyber using a Monte Carlo Markov Chain discrete Gaussian sampler. Our main contribution is to clearly identify a set of parameters under which our attack (and presumably other recent dual attacks) can work. Furthermore, our analysis completely departs from the existing statistics-based analysis and is instead rooted in geometry. We also compare the regime in which our algorithm works to the ``contradictory regime'' of [Ducas and Pulles,2023]. We observe that those two regimes are essentially complementary. Finally, we give a quantum version of our algorithm to speed up the computation. The algorithm is inspired by [Albrecht, and Shen,2022] but is completely formal and does not rely on any heuristics.

Note: Add complexity estimates of our simplified attack using a Monte Carlo Markov Chain-based Discrete Gaussian sampler. Many clarifications and small corrections.

Available format(s)
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in EUROCRYPT 2024
Learning with ErrorsDual attackLattice-based cryptography
Contact author(s)
amaury pouly @ cnrs fr
yixin shen @ kcl ac uk
2024-02-21: last of 2 revisions
2023-10-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Amaury Pouly and Yixin Shen},
      title = {Provable Dual Attacks on Learning with Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1508},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.