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

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

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

9 Citations (Scopus)
277 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the 56th Annual Design Automation Conference 2019, DAC 2019
PublisherAssociation for Computing Machinery (ACM)
Pages88:1-88:6
Number of pages6
ISBN (Electronic)978-1-4503-6725-7
DOIs
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
Country/TerritoryUnited States
CityLas Vegas, NV
Period2/06/196/06/19

Keywords

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

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modelling and Simulation

Fingerprint

Dive into the research topics of 'Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on the Falcon signature scheme'. Together they form a unique fingerprint.

Cite this