Paper 2023/1850

Accurate Score Prediction for Dual-Sieve Attacks

Léo Ducas, Centrum Wiskunde & Informatica, Leiden University
Ludo N. Pulles, Centrum Wiskunde & Informatica
Abstract

The Dual-Sieve Attack on Learning with Errors (LWE), or more generally Bounded Distance Decoding (BDD), has seen many improvements in the recent years, and ultimately led to claims that it outperforms the primal attack against certain lattice-based schemes in the PQC standardization process organised by NIST. However, the work of Ducas--Pulles (Crypto '23) revealed that the so-called "Independence Heuristic", which all recent dual attacks used, leads to wrong predictions in a contradictory regime, which is relevant for the security of cryptoschemes. More specifically, the stated distributions of scores for the actual solution and for incorrect candidates were both incorrect. In this work, we propose to use the weaker heuristic that the output vectors of a lattice sieve are uniformly distributed in a ball. Under this heuristic, we give an analysis of the score distribution in the case of an error of fixed length. Integrating over this length, we extend this analysis to any radially distributed error, in particular the gaussian as a fix for the score distribution of the actual solution. This approach also provides a prediction for the score of incorrect candidates, using a ball as an approximation of the Voronoi cell of a lattice. We compare the predicted score distributions to extensive experiments, and observe them to be qualitatively and quantitatively quite accurate. This constitutes a first step towards fixing the analysis of the dual-sieve attack: we can now accurately estimate false-positives and false-negatives. Now that the analysis is fixed, one may consider how to fix the attack itself, namely exploring the opportunities to mitigate a large number of false-positives.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
LatticesCryptanalysisHeuristicsLearning with ErrorsDual AttackBessel Functions
Contact author(s)
ducas @ cwi nl
Ludo Pulles @ cwi nl
History
2023-12-04: approved
2023-12-01: received
See all versions
Short URL
https://ia.cr/2023/1850
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2023/1850,
      author = {Léo Ducas and Ludo N. Pulles},
      title = {Accurate Score Prediction for Dual-Sieve Attacks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1850},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1850}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.