Constant-time discrete Gaussian sampling

Angshuman Karmakar, Sujoy Sinha Roy, Oscar Reparaz, Frederik Vercauteren, Ingrid Verbauwhede

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)
252 Downloads (Pure)


Sampling from a discrete Gaussian distribution is an indispensable part of lattice-based cryptography. Several recent works have shown that the timing leakage from a non-constant-time implementation of the discrete Gaussian sampling algorithm could be exploited to recover the secret. In this paper, we propose a constant-time implementation of the Knuth-Yao random walk algorithm for performing constant-time discrete Gaussian sampling. Since the random walk is dictated by a set of input random bits, we can express the generated sample as a function of the input random bits. Hence, our constant-time implementation expresses the unique mapping of the input random-bits to the output sample-bits as a Boolean expression of the random-bits. We use bit-slicing to generate multiple samples in batches and thus increase the throughput of our constant-time sampling manifold. Our experiments on an Intel i7-Broadwell processor show that our method can be as much as 2.4 times faster than the constant-time implementation of cumulative distribution table based sampling and consumes exponentially less memory than the Knuth-Yao algorithm with shuffling for a similar level of security.
Original languageEnglish
Pages (from-to)1561-1571
JournalIEEE Transactions on Computers
Issue number11
Early online date12 Mar 2018
Publication statusPublished - 1 Nov 2018


  • Knuth-Yao
  • Constant-time sampling
  • Lattice-based cryptography
  • Discrete Gaussian Sampling


Dive into the research topics of 'Constant-time discrete Gaussian sampling'. Together they form a unique fingerprint.

Cite this