EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Accurate Score Prediction for Dual-Sieve Attacks

Léo Ducas, Ludo N. Pulles

Journal of Cryptology · 2026-01 · 39 (1)

DOI: 10.1007/s00145-025-09560-7 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Cryptology, online erschienen am 20.11.2025. Verfasst von Léo Ducas und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 49 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Guo and Johansson (ASIACRYPT 2021), and MATZOV (tech. report 2022) have independently claimed improved attacks against various NIST lattice candidates by using a Fast Fourier Transform (FFT) on top of the so-called Dual-Sieve attack. However, we will show that a heuristic used in above works not only theoretically contradicts with both formal theorems and well-tested heuristics in certain regimes, but also provides incorrect predictions experimentally. We conclude that this heuristic significantly overestimates the success probability of the Dual-Sieve attack. Alternatively, we propose a seemingly weaker heuristic for the output of a lattice sieve. When determining part of the secret in the Dual-Sieve attack, we derive predictions for the score distribution associated to candidates using this heuristic: for correct candidates with noise drawn from any radial distribution, we derive score predictions using a central limit heuristic; for incorrect candidates, we derive score predictions by approximating the Voronoi cell by a ball. In the process, we show that the use of the FFT is not specific to Learning with Errors (LWE) but is more generally useful against the Bounded Distance Decoding problem (BDD). Ultimately, we compare the predicted score distributions with extensive experiments, and observe these predictions to be qualitatively and quantitatively quite accurate. This makes it possible to accurately estimate the number of false positives and false negatives, opening the door for a sound analysis of the Dual-Sieve attack. In particular, one may consider exploring the opportunities to mitigate a large number of false positives. 1

Zitieren

APA

Ducas, L., & Pulles, L. N. (2026). Accurate Score Prediction for Dual-Sieve Attacks. Journal of Cryptology, 39(1). https://doi.org/10.1007/s00145-025-09560-7

Vancouver

Ducas L, Pulles LN. Accurate Score Prediction for Dual-Sieve Attacks. Journal of Cryptology. 2026;39(1). doi:10.1007/s00145-025-09560-7

BibTeX
@article{Ducas2026,
  author = {Ducas, Léo and Pulles, Ludo N.},
  title = {Accurate Score Prediction for Dual-Sieve Attacks},
  journal = {Journal of Cryptology},
  year = {2026},
  volume = {39},
  number = {1},
  doi = {10.1007/s00145-025-09560-7}
}
Kostenlos starten →