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
-
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},
note = {\url{https://eprint.iacr.org/2019/267}},
url = {https://eprint.iacr.org/2019/267}
}
