Constant-time discrete Gaussian sampling

Research output: Contribution to journalArticlepeer-review

Authors

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

Colleges, School and Institutes

External organisations

  • KU Leuven ESAT/COSIC and Imec, Leuven-Heverlee, Belgium
  • KU Leuven ESAT/COSIC and Imec, Leuven-Heverlee, Belgium

Abstract

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.

Details

Original languageEnglish
Pages (from-to)1561-1571
JournalIEEE Transactions on Computers
Volume67
Issue number11
Early online date12 Mar 2018
Publication statusPublished - 1 Nov 2018

Keywords

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