Paper 2017/988

On Rejection Sampling Algorithms for Centered Discrete Gaussian Distribution over Integers

Yusong Du and Baodian Wei

Abstract

Lattice-based cryptography has been accepted as a promising candidate for public key cryptography in the age of quantum computing. Discrete Gaussian sampling is one of fundamental operations in many lattice-based cryptosystems. In this paper, we discuss a sub-problem of discrete Gaussian sampling, which is to sample from a centered discrete Gaussian distribution over the integers with positive standard deviation and zero center. We propose three alternative rejection sampling algorithms for centered discrete Gaussian distributions with standard deviation in two specific forms. The first algorithm is designed for the case where the standard deviation is an positive integer, and it requires neither pre-computation storage nor floating-point arithmetic. While the other two algorithms are fit for a standard deviation that is an integer multiple of a fixed real number (approximately equal to 0.849). These two algorithms require fixed look-up tables of very small size (e.g. 128 bits and 320 bits respectively), but they are much more efficient than the first algorithm. The experimental results show that our algorithms have better performance than that of two rejection sampling algorithms proposed by Karney in 2016 and by Ducas et al.\ in 2013 respectively. The expected numbers of random bits used in our algorithms are significantly smaller than that of random bits used in Karney's rejection sampling algorithm.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
lattice-based cryptographydiscrete Gaussian samplingrejection sampling
Contact author(s)
duyusong @ mail sysu edu cn
History
2017-10-11: received
Short URL
https://ia.cr/2017/988
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/988,
      author = {Yusong Du and Baodian Wei},
      title = {On Rejection Sampling Algorithms for Centered Discrete Gaussian Distribution over Integers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/988},
      year = {2017},
      url = {https://eprint.iacr.org/2017/988}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.