Paper 2019/267

Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on Falcon.

Angshuman Karmakar, Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede


Sampling from discrete Gaussian distribution has applications in lattice-based post-quantum cryptography. Several efficient solutions have been proposed in recent years. However, making a Gaussian sampler secure against timing attacks turned out to be a challenging research problem. In this work, we observed an important property of the input random bit strings that generate samples in Knuth-Yao sampling. We delineate a generic step-by-step method to instantiate a discrete Gaussian sampler of arbitrary standard deviation and precision by efficiently minimizing the Boolean expressions by exploiting this prop- erty. Discrete Gaussian samplers generated in this method can be up to 37% faster than the state of the art method. Finally, we show that the signing algorithm of post-quantum signature scheme Falcon using our constant-time sampler is at most 33% slower than the fastest non-constant time sampler.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. DAC 2019
Post-quantum signatureFalconconstant-timediscrete Gaussianbit-slice
Contact author(s)
angshuman karmakar @ esat kuleuven be
2019-05-02: last of 4 revisions
2019-03-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Angshuman Karmakar and Sujoy Sinha Roy and Frederik Vercauteren and Ingrid Verbauwhede},
      title = {Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on Falcon.},
      howpublished = {Cryptology ePrint Archive, Paper 2019/267},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.