Paper 2017/259

Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time

Daniele Micciancio and Michael Walter

Abstract

Sampling integers with Gaussian distribution is a fundamental problem that arises in almost every application of lattice cryptography, and it can be both time consuming and challenging to implement. Most previous work has focused on the optimization and implementation of integer Gaussian sampling in the context of specific applications, with fixed sets of parameters. We present new algorithms for discrete Gaussian sampling that are both generic (application independent), efficient, and more easily implemented in constant time without incurring a substantial slow-down, making them more resilient to side-channel (e.g., timing) attacks. As an additional contribution, we present new analytical techniques that can be used to simplify the precision/security evaluation of floating point cryptographic algorithms, and an experimental comparison of our algorithms with previous algorithms from the literature.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
A minor revision of an IACR publication in CRYPTO 2017
Keywords
Lattice-Based CryptographyDiscrete Gaussian Sampling
Contact author(s)
miwalter @ eng ucsd edu
History
2018-02-06: last of 4 revisions
2017-03-25: received
See all versions
Short URL
https://ia.cr/2017/259
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/259,
      author = {Daniele Micciancio and Michael Walter},
      title = {Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time},
      howpublished = {Cryptology ePrint Archive, Paper 2017/259},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/259}},
      url = {https://eprint.iacr.org/2017/259}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.