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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

External organisations

  • imec-COSIC, KU Leuven, Leuven-Heverlee, Belgium

Abstract

Sampling from a 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 present a toolchain to instantiate an efficient constant-time discrete Gaussian sampler of arbitrary standard deviation and precision. We observe an interesting property of the mapping from input random bit strings to samples during a Knuth-Yao sampling algorithm and propose an efficient way of minimizing the Boolean expressions for the mapping. Our minimization approach results in up to 37% faster discrete Gaussian sampling compared to the previous work. Finally, we apply our optimized and secure Gaussian sampler in the lattice-based digital signature algorithm Falcon, which is a NIST submission, and provide experimental evidence that the overall performance of the signing algorithm degrades by at most 33% only due to the additional overhead of 'constant-time' sampling, including the 60% overhead of random number generation. Breaking a general belief, our results indirectly show that the use of discrete Gaussian samples in digital signature algorithms would be beneficial.

Details

Original languageEnglish
Title of host publicationProceedings of the 56th Annual Design Automation Conference 2019, DAC 2019
Publication statusPublished - 2 Jun 2019
Eventthe 56th Annual Design Automation Conference 2019 - Las Vegas, NV, United States
Duration: 2 Jun 20196 Jun 2019

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Conference

Conferencethe 56th Annual Design Automation Conference 2019
CountryUnited States
CityLas Vegas, NV
Period2/06/196/06/19

Keywords

  • Discrete Gaussian, Constant-time, Boolean minimization, Learning with errors