Paper 2024/1791 Original: eprint.iacr.org/2024/1791 ↗
Discrete gaussian sampling for BKZ-reduced basis
Abstract
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2025-01-23: last updated
- 2024-11-02: published
- Short URL
- https://ia.cr/2024/1791
- License
- https://creativecommons.org/licenses/by-sa/4.0/
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}
}