Paper 2024/1791
Discrete gaussian sampling for BKZ-reduced basis
, French National Centre for Scientific Research, Univ Rennes, Inria, CNRS, IRISA, Rennes, FranceAbstract
Discrete Gaussian sampling on lattices is a fundamental problem in lattice-based cryptography. In this paper, we revisit the Markov chain Monte Carlo (MCMC)-based Metropolis-Hastings-Klein (MHK) algorithm proposed by Wang and Ling and study its complexity under the Geometric Series Assuption (GSA) when the given basis is BKZ-reduced. We give experimental evidence that the GSA is accurate in this context, and we give a very simple approximate formula for the complexity of the sampler that is accurate over a large range of parameters and easily computable. We apply our results to the dual attack on LWE of [Pouly and Shen 2024] and significantly improve the complexity estimates of the attack. Finally, we provide some results of independent interest on the Gaussian mass of a random $q$-ary lattices.
Note: The code to produce the figures is available upon request and will be made public at a later stage.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- LatticesDiscrete Gaussian SamplingGeometric Series Assumption
- Contact author(s)
-
amaury pouly @ cnrs fr
yixin shen @ inria fr - History
- 2024-11-04: approved
- 2024-11-02: received
- See all versions
- Short URL
- https://ia.cr/2024/1791
- License
-
CC BY-SA
BibTeX
@misc{cryptoeprint:2024/1791,
author = {Amaury Pouly and Yixin Shen},
title = {Discrete gaussian sampling for {BKZ}-reduced basis},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1791},
year = {2024},
url = {https://eprint.iacr.org/2024/1791}
}
