Paper 2023/302

Does the Dual-Sieve Attack on Learning with Errors even Work?

Léo Ducas, Centrum Wiskunde & Informatica
Ludo Pulles, Centrum Wiskunde & Informatica

Guo and Johansson (ASIACRYPT 2021), and MATZOV (tech.~report 2022) have independently claimed improved attacks against various NIST lattice candidate by adding a Fast Fourier Transform (FFT) trick on top of the so-called Dual-Sieve attack. Recently, there was more follow up work in this line adding new practical improvements. However, from a theoretical perspective, all of these works are painfully specific to Learning with Errors, while the principle of the Dual-Sieve attack is more general (Laarhoven & Walter, CT-RSA 2021). More critically, all of these works are based on heuristics that have received very little theoretical and experimental attention. This work attempts to rectify the above deficiencies of the literature. We first propose a generalization of the FFT trick by Guo and Johansson to arbitrary Bounded Distance Decoding instances. This generalization offers a new improvement to the attack. We then theoretically explore the underlying heuristics and show that these are in contradiction with formal, unconditional theorems in some regimes, and with well-tested heuristics in other regimes. The specific instantiations of the recent literature fall into this second regime. We confirm these contradictions with experiments, documenting several phenomena that are not predicted by the analysis, including a ``waterfall-floor'' phenomenon, reminiscent of Low-Density Parity-Check decoding failures. We conclude that the success probability of the recent Dual-Sieve-FFT attacks are presumably significantly overestimated. We further discuss the adequate way forward towards fixing the attack and its analysis.

Available format(s)
Publication info
LatticesCryptanalysisHeuristicsLearning with ErrorsDual AttackFast Fourier Transform
Contact author(s)
ducas @ cwi nl
Ludo Pulles @ cwi nl
2023-03-01: approved
2023-02-28: received
See all versions
Short URL
No rights reserved


      author = {Léo Ducas and Ludo Pulles},
      title = {Does the Dual-Sieve Attack on Learning with Errors even Work?},
      howpublished = {Cryptology ePrint Archive, Paper 2023/302},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.