Paper 2022/922

Estimating the Hidden Overheads in the BDGL Lattice Sieving Algorithm

Léo Ducas, Centrum Wiskunde & Informatica
Abstract

The lattice sieving algorithm based on list-decoding of Becker-Ducas-Gama-Laarhoven (SODA 2016) is currently at the center of cryptanalysis cost estimates of candidate lattice schemes for post-quantum standardization. Yet, only an idealized version of this algorithm has been carefully modelled, i.e. given an efficient list-decoding oracle for a perfectly random spherical code. In this work, we propose an experimental analysis of the actual algorithm. The difficulty lies in estimating the probabilistic defect with respect to perfectly random spherical codes for the task at hand. While it should be in principle infeasible to run the algorithm in cryptographically relevant dimensions, a few tricks allow to nevertheless measure experimentally the relevant quantity. Concretely, we conclude on an overhead factor of about $2^{6}$ on the number of gates in the RAM model compared to the idealized model for dimensions around $380$ after an appropriate re-parametrization. Part of this overhead can be traded for extra memory, at a costly rate. We also clarify that these overheads apply to an internal routine, and discuss how they can be partially mitigated in the whole attack.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. PQ Crypto 2022
Keywords
Concrete Cryptanalysis Lattice Sieving
Contact author(s)
ducas @ cwi nl
History
2022-07-15: approved
2022-07-15: received
See all versions
Short URL
https://ia.cr/2022/922
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/922,
      author = {Léo Ducas},
      title = {Estimating the Hidden Overheads in the BDGL Lattice Sieving Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2022/922},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/922}},
      url = {https://eprint.iacr.org/2022/922}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.