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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. DAC 2019
Keywords
Post-quantum signatureFalconconstant-timediscrete Gaussianbit-slice
Contact author(s)
angshuman karmakar @ esat kuleuven be
History
2019-05-02: last of 4 revisions
2019-03-06: received
See all versions
Short URL
https://ia.cr/2019/267
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/267,
      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},
      url = {https://eprint.iacr.org/2019/267}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.