Cryptology ePrint Archive: Report 2019/267

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

Angshuman Karmakar and Sujoy Sinha Roy and 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.

Category / Keywords: public-key cryptography / Post-quantum signature, Falcon, constant-time, discrete Gaussian, bit-slice

Original Publication (with minor differences): DAC 2019

Date: received 5 Mar 2019, last revised 2 May 2019

Contact author: angshuman karmakar at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20190502:145132 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]