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

Science China Information Sciences

Error estimation of practical convolution discrete Gaussian sampling with rejection sampling

Zhongxiang Zheng, Xiaoyun Wang, Guangwu Xu, Chunhuan Zhao

Published Feb 4, 2021• 2 citations
Publisher
DOI
10.1007/s11432-019-9919-7

Related papers

The influence of non-Gaussian noise on the accuracy of parameter estimation

Xuelian Li, Jungang Li, Yuanmei Wang

Physics Letters A•Nov 2, 2016•6 citations

Improved Dual Attack and Trapdoor Sampling via Quantum Rejection Sampling

Cong Ling, Hao Yan, Nicholas Zhao

In this work, we revisit the dual attack and GPV trapdoor sampling, focusing on the lattice Gaussian sampling term, which can be a significant bottleneck in the overall complexity. We show that this sampling step can be quantumly accelerated by combining the lower bound underlying Wang and Ling's analysis of Klein's algorithm with the quantum rejection sampling (QRS) framework proposed by Ozols et al. Specifically, this lower bound gives precisely the pointwise domination condition required for quantum rejection sampling when given coherent oracle access to a truncated Klein proposal distribution, which yields a quantum procedure for preparing the truncated dual $q$-ary lattice Gaussian with a quadratic reduction in the sampling complexity. The truncation radius is chosen so that the truncated distribution is negligibly close to the full lattice Gaussian in total variation distance. Substituting this sampler into the dual attack framework results in reduced overall attack-cost estimates. Compared with Pouly and Shen's modern dual attack under the same parameter choices, our estimates reduce the attack cost by \(9\), \(4\), and \(13\) bits for Kyber-512, Kyber-768, and Kyber-1024, respectively. We also report the corresponding estimates with modulus switching. Finally, by replacing the Markov chain Monte Carlo (MCMC) sampler with the QRS algorithm, we achieve a similar quadratic speedup in the GPV signing process.

quant-pharXiv:2605.24798•May 26, 2026•1 citation

Exact Lattice Sampling from Non-Gaussian Distributions

Maxime Plançon, Thomas Prest

Lecture notes in computer science•Jan 1, 2021•5 citations

Adaptive Greedy Rejection Sampling

Gergely Flamich, Lucas Theis

We consider channel simulation protocols between two communicating parties, Alice and Bob. First, Alice receives a target distribution Q, unknown to Bob. Then, she employs a shared coding distribution P to send the minimum amount of information to Bob so that he can simulate a single sample X ~ Q. For discrete distributions, Harsha et al. [1] developed a well-known channel simulation protocol – greedy rejection sampling (GRS) – with a bound of ${D_{{\text{KL}}}}\left[ {Q\left\| P \right.} \right] + 2\ln \left( {{D_{{\text{KL}}}}\left[ {Q\left\| P \right.} \right] + 1} \right) + \mathcal{O}\left( 1 \right)$ on the expected code-length of the protocol. In this paper, we extend the definition of GRS to general probability spaces and allow it to adapt its proposal distribution after each step. We call this new procedure Adaptive GRS (AGRS) and prove its correctness. Furthermore, we prove the surprising result that the expected runtime of GRS is exactly exp(D∞[Q║P]), where D∞[Q║P] denotes the Rényi ∞-divergence. We then apply AGRS to Gaussian channel simulation problems. We show that the expected runtime of GRS is infinite when averaged over target distributions and propose a solution that trades off a slight increase in the coding cost for a finite runtime. Finally, we describe a specific instance of AGRS for 1D Gaussian channels inspired by hybrid coding [2]. We conjecture and demonstrate empirically that the runtime of AGRS is $\mathcal{O}\left( {{D_{KL}}\left[ {Q\left\| P \right.} \right]} \right)$ in this case.

arXiv:2304.10407•IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•14 citations

Fourier transform convolutional error-correcting codes

T.G. Marshall

Asilomar Conference on Signals, Systems and Computers (ACSSC)•Jan 1, 1989•8 citations

A New Lattice-Based Post-Quantum Digital Signature from Compact Rejection Sampling

Pingyuan Zhang, Limin Wang

Rejection samplings are the essential building blocks to design lattice-based digital signatures under the Fiat–Shamir paradigm. Up to now most of them have been built by Gaussian samplings or uniform samplings. Gaussian-based rejection sampling signatures such as the BLISS scheme have very short signature sizes but are vulnerable to timing attacks, whereas the uniform-based rejection sampling signatures such as ML-DSA are allowed to be simply implemented but have larger signature sizes. This work intends to use a new probability distribution, rather than Gaussian or uniform distributions, to build the rejection sampling in Fiat–Shamir signatures, and aims to achieve short signature sizes while avoiding the cost of Gaussian sampling. To this end, we choose centered binomial distribution as a replacement, and build a new and compact rejection sampling that has the properties of both high-precision sampling and semi-uniform operation. As an application, we combine this rejection sampling with Lyubashevsky’s signature scheme, then propose the first lattice-based Fiat–Shamir signature scheme from centered binomial distribution. The proposed scheme not only avoids Gaussian sampling, but also is very efficient in terms of the signature sizes.

Computers•Aug 19, 2026•0 citations
In this work, we revisit the dual attack and GPV trapdoor sampling, focusing on the lattice Gaussian sampling term, which can be a significant bottleneck in the overall complexity. We show that this sampling step can be quantumly accelerated by combining the lower bound underlying Wang and Ling's analysis of Klein's algorithm with the quantum rejection sampling (QRS) framework proposed by Ozols et al. Specifically, this lower bound gives precisely the pointwise domination condition required for quantum rejection sampling when given coherent oracle access to a truncated Klein proposal distribution, which yields a quantum procedure for preparing the truncated dual qqq-ary lattice Gaussian with a quadratic reduction in the sampling complexity. The truncation radius is chosen so that the truncated distribution is negligibly close to the full lattice Gaussian in total variation distance. Substituting this sampler into the dual attack framework results in reduced overall attack-cost estimates. Compared with Pouly and Shen's modern dual attack under the same parameter choices, our estimates reduce the attack cost by 999, 444, and 131313 bits for Kyber-512, Kyber-768, and Kyber-1024, respectively. We also report the corresponding estimates with modulus switching. Finally, by replacing the Markov chain Monte Carlo (MCMC) sampler with the QRS algorithm, we achieve a similar quadratic speedup in the GPV signing process.
We consider channel simulation protocols between two communicating parties, Alice and Bob. First, Alice receives a target distribution Q, unknown to Bob. Then, she employs a shared coding distribution P to send the minimum amount of information to Bob so that he can simulate a single sample X ~ Q. For discrete distributions, Harsha et al. [1] developed a well-known channel simulation protocol – greedy rejection sampling (GRS) – with a bound of DKL[Q∥P]+2ln⁡(DKL[Q∥P]+1)+O(1){D_{{\text{KL}}}}\left[ {Q\left\| P \right.} \right] + 2\ln \left( {{D_{{\text{KL}}}}\left[ {Q\left\| P \right.} \right] + 1} \right) + \mathcal{O}\left( 1 \right)DKL​[Q∥P]+2ln(DKL​[Q∥P]+1)+O(1) on the expected code-length of the protocol. In this paper, we extend the definition of GRS to general probability spaces and allow it to adapt its proposal distribution after each step. We call this new procedure Adaptive GRS (AGRS) and prove its correctness. Furthermore, we prove the surprising result that the expected runtime of GRS is exactly exp(D∞[Q║P]), where D∞[Q║P] denotes the Rényi ∞-divergence. We then apply AGRS to Gaussian channel simulation problems. We show that the expected runtime of GRS is infinite when averaged over target distributions and propose a solution that trades off a slight increase in the coding cost for a finite runtime. Finally, we describe a specific instance of AGRS for 1D Gaussian channels inspired by hybrid coding [2]. We conjecture and demonstrate empirically that the runtime of AGRS is O(DKL[Q∥P])\mathcal{O}\left( {{D_{KL}}\left[ {Q\left\| P \right.} \right]} \right)O(DKL​[Q∥P]) in this case.
Rejection samplings are the essential building blocks to design lattice-based digital signatures under the Fiat–Shamir paradigm. Up to now most of them have been built by Gaussian samplings or uniform samplings. Gaussian-based rejection sampling signatures such as the BLISS scheme have very short signature sizes but are vulnerable to timing attacks, whereas the uniform-based rejection sampling signatures such as ML-DSA are allowed to be simply implemented but have larger signature sizes. This work intends to use a new probability distribution, rather than Gaussian or uniform distributions, to build the rejection sampling in Fiat–Shamir signatures, and aims to achieve short signature sizes while avoiding the cost of Gaussian sampling. To this end, we choose centered binomial distribution as a replacement, and build a new and compact rejection sampling that has the properties of both high-precision sampling and semi-uniform operation. As an application, we combine this rejection sampling with Lyubashevsky’s signature scheme, then propose the first lattice-based Fiat–Shamir signature scheme from centered binomial distribution. The proposed scheme not only avoids Gaussian sampling, but also is very efficient in terms of the signature sizes.