Paper 2026/984
Quantum algorithm for Discrete Gaussian Sampling
, Univ Rennes, Inria, CNRS, IRISA, Univ Rennes, Inria, CNRS, IRISAAbstract
Discrete Gaussian Sampling on lattices is a fundamental problem in lattice-based cryptography. It appears both in basic cryptographic primitives such as digital signatures and as an important cryptanalysis building block for solving hard lattice problems. In this paper, we show a quantum algorithm based on the quantum rejection sampling technique whose complexity is asymptotically quadratically faster than its classical counterpart in [Wang \& Ling, IEEE Trans. Inf. Theory 2019]. Our sampler outputs a quantum state which can either be measured to get the desired distribution or be used directly as such in other quantum algorithms. By doing so, we derive two versions of quantum dual attacks that improve upon the previous ones in [Pouly \& Shen, EUROCRYPT 2024]. The two versions are incomparable, each having distinct advantages (speed vs memory requirement). The second version is particularly interesting as it requires only polynomial classical and quantum memory, excluding the classical memory used in the preprocessing step of the Discrete Gaussian sampler. Our quantum Discrete Gaussian sampler can also be used to speed up the algorithm for solving the Short Integer Solution problem, in any norm, of [Bollauf, Pouly \& Shen, ePrint 2026/225].
Note: Revision. (A previous version of the paper was submitted to CRYPTO 2026.)
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Quantum cryptanalysisLattice-based cryptographyQuantum rejection samplingDiscrete Gaussian Sampling
- Contact author(s)
-
clemence chevignard @ inria fr
andre schrottenloher @ inria fr
yixin shen @ inria fr - History
- 2026-05-19: revised
- 2026-05-18: received
- See all versions
- Short URL
- https://ia.cr/2026/984
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/984,
author = {Clémence Chevignard and André Schrottenloher and Yixin Shen},
title = {Quantum algorithm for Discrete Gaussian Sampling},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/984},
year = {2026},
url = {https://eprint.iacr.org/2026/984}
}
