Paper 2018/1234

FACCT: FAst, Compact, and Constant-Time Discrete Gaussian Sampler over Integers

Raymond K. Zhao, Ron Steinfeld, and Amin Sakzad

Abstract

The discrete Gaussian sampler is one of the fundamental tools in implementing lattice-based cryptosystems. However, a naive discrete Gaussian sampling implementation suffers from side-channel vulnerabilities, and the existing countermeasures usually introduce significant overhead in either the running speed or the memory consumption. In this paper, we propose a fast, compact, and constant-time implementation of the binary sampling algorithm, originally introduced in the BLISS signature scheme. Our implementation adapts the Rényi divergence and the transcendental function polynomial approximation techniques. The efficiency of our scheme is independent of the standard deviation, and we show evidence that our implementations are either faster or more compact than several existing constant-time samplers. In addition, we show the performance of our implementation techniques applied to and integrated with two existing signature schemes: qTesla and Falcon. On the other hand, the convolution theorems are typically adapted to sample from larger standard deviations, by combining samples with much smaller standard deviations. As an additional contribution, we show better parameters for the convolution theorems.

Note: Update the link to the source code.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. IEEE Transactions on Computers
DOI
10.1109/TC.2019.2940949
Keywords
Lattice-based cryptodiscrete Gaussian samplingconstant-timeimplementationefficiency
Contact author(s)
raymond zhao @ monash edu
History
2020-09-25: last of 5 revisions
2018-12-31: received
See all versions
Short URL
https://ia.cr/2018/1234
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1234,
      author = {Raymond K.  Zhao and Ron Steinfeld and Amin Sakzad},
      title = {FACCT: FAst, Compact, and Constant-Time Discrete Gaussian Sampler over Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1234},
      year = {2018},
      doi = {10.1109/TC.2019.2940949},
      note = {\url{https://eprint.iacr.org/2018/1234}},
      url = {https://eprint.iacr.org/2018/1234}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.