Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography

Nicholas Genise, Daniele Micciancio, Chris Peikert, Michael Walter

Published Jan 1, 2020• 47 citations
Publisher
DOI
10.1007/978-3-030-45374-9_21

Related papers

A Survey on Discrete Gaussian Samplers in Lattice Based Cryptography

Jiaxin Deng, Simin Chen, Jiageng Chen +1 more

Communications in computer and information science•Jan 1, 2022•0 citations

Gaussian Sampling Precision and Information Leakage in Lattice Cryptography.

Markku-Juhani Olavi Saarinen

•Jan 1, 2015•11 citations

Discrete Gaussians Modulo Sub-Lattices: New Leftover Hash Lemmas for Discrete Gaussians

Haoxiang Jin, Feng-Hao Liu, Zhedong Wang +1 more

Lecture notes in computer science•Jan 1, 2025•4 citations

Quantum algorithm for Discrete Gaussian Sampling

Clémence Chevignard, Yixin Shen, André Schrottenloher

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].

quant-pharXiv:2605.20133•May 20, 2026•0 citations

Gaussian Sampling in Lattice-Based Cryptography

Thomas Prest

Although rather recent, lattice-based cryptography has stood out on numerous points, be it by the variety of constructions that it allows, by its expected resistance to quantum computers, of by its efficiency when instantiated on some classes of lattices. One of the most powerful tools of lattice-based cryptography is Gaussian sampling. At a high level, it allows to prove the knowledge of a particular lattice basis without disclosing any information about this basis. It allows to realize a wide array of cryptosystems. Somewhat surprisingly, few practical instantiations of such schemes are realized, and the algorithms which perform Gaussian sampling are seldom studied. The goal of this thesis is to fill the gap between the theory and practice of Gaussian sampling. First, we study and improve the existing algorithms, byboth a statistical analysis and a geometrical approach. We then exploit the structures underlying many classes of lattices and apply the ideas of the fast Fourier transform to a Gaussian sampler, allowing us to reach a quasilinearcomplexity instead of quadratic. Finally, we use Gaussian sampling in practice to instantiate a signature scheme and an identity-based encryption scheme. The first one yields signatures that are the most compact currently obtained in lattice-based cryptography, and the second one allows encryption and decryption that are about one thousand times faster than those obtained with a pairing-based counterpart on elliptic curves.

•Dec 8, 2015•25 citations

Quantum attack-resistant signature scheme from lattice cryptography for WFH

Luyao Wang, Chunguang Huang, Hai Ying Cheng

With the emergence of quantum computers, traditional digital signature schemes based on problems such as large integer solutions and discrete logarithms will no longer be secure, and it is urgent to find effective digital signature schemes that can resist quantum attacks. Lattice cryptography has the advantages of computational simplicity and high security. In this paper, we propose an identity-based digital signature scheme based on the rejection sampling algorithm. Unlike most schemes that use a common Gaussian distribution, this paper uses a bimodal Gaussian distribution, which improves efficiency. The identity-based signature scheme is more convenient for practical application than the traditional certificate-based signature scheme.

International Conference on Big Data, Artificial Intelligence and Internet of Things Engineering (ICBAIE)•Mar 26, 2021•7 citations
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].
Although rather recent, lattice-based cryptography has stood out on numerous points, be it by the variety of constructions that it allows, by its expected resistance to quantum computers, of by its efficiency when instantiated on some classes of lattices. One of the most powerful tools of lattice-based cryptography is Gaussian sampling. At a high level, it allows to prove the knowledge of a particular lattice basis without disclosing any information about this basis. It allows to realize a wide array of cryptosystems. Somewhat surprisingly, few practical instantiations of such schemes are realized, and the algorithms which perform Gaussian sampling are seldom studied. The goal of this thesis is to fill the gap between the theory and practice of Gaussian sampling. First, we study and improve the existing algorithms, byboth a statistical analysis and a geometrical approach. We then exploit the structures underlying many classes of lattices and apply the ideas of the fast Fourier transform to a Gaussian sampler, allowing us to reach a quasilinearcomplexity instead of quadratic. Finally, we use Gaussian sampling in practice to instantiate a signature scheme and an identity-based encryption scheme. The first one yields signatures that are the most compact currently obtained in lattice-based cryptography, and the second one allows encryption and decryption that are about one thousand times faster than those obtained with a pairing-based counterpart on elliptic curves.
With the emergence of quantum computers, traditional digital signature schemes based on problems such as large integer solutions and discrete logarithms will no longer be secure, and it is urgent to find effective digital signature schemes that can resist quantum attacks. Lattice cryptography has the advantages of computational simplicity and high security. In this paper, we propose an identity-based digital signature scheme based on the rejection sampling algorithm. Unlike most schemes that use a common Gaussian distribution, this paper uses a bimodal Gaussian distribution, which improves efficiency. The identity-based signature scheme is more convenient for practical application than the traditional certificate-based signature scheme.