TY - GEN
T1 - Discrete Gaussian Sampling for BKZ-Reduced Basis
AU - Pouly, Amaury
AU - Shen, Yixin
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.
PY - 2025/1/1
Y1 - 2025/1/1
N2 - 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 Assumption (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 [24] 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.
AB - 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 Assumption (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 [24] 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.
KW - Discrete Gaussian Sampling
KW - Geometric Series Assumption
KW - Lattices
UR - https://www.scopus.com/pages/publications/105002138977
U2 - 10.1007/978-3-031-86602-9_3
DO - 10.1007/978-3-031-86602-9_3
M3 - Conference contribution
AN - SCOPUS:105002138977
SN - 9783031866012
T3 - Lecture Notes in Computer Science
SP - 63
EP - 88
BT - Post-Quantum Cryptography - 16th International Workshop, PQCrypto 2025, Proceedings
A2 - Niederhagen, Ruben
A2 - Saarinen, Markku-Juhani O.
PB - Springer Science and Business Media Deutschland GmbH
T2 - 16th International Workshop on Post-Quantum Cryptography, PQCrypto 2025
Y2 - 8 April 2025 through 10 April 2025
ER -