Paper 2013/510

Discrete Ziggurat: A Time-Memory Trade-off for Sampling from a Gaussian Distribution over the Integers

Johannes Buchmann, Daniel Cabarcas, Florian Göpfert, Andreas Hülsing, and Patrick Weiden

Abstract

Several lattice-based cryptosystems require to sample from a discrete Gaussian distribution over the integers. Existing methods to sample from such a distribution either need large amounts of memory or they are very slow. In this paper we explore a different method that allows for a flexible time-memory trade-off, offering developers freedom in choosing how much space they can spare to store precomputed values. We prove that the generated distribution is close enough to a discrete Gaussian to be used in lattice-based cryptography. Moreover, we report on an implementation of the method and compare its performance to existing methods from the literature. We show that for large standard deviations, the Ziggurat algorithm outperforms all existing methods.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision.Selected Areas in Cryptography 2013
Keywords
Lattice-Based CryptographyGaussian SamplingPracticalityImplementation
Contact author(s)
pweiden @ cdc informatik tu-darmstadt de
History
2013-08-17: received
Short URL
https://ia.cr/2013/510
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/510,
      author = {Johannes Buchmann and Daniel Cabarcas and Florian Göpfert and Andreas Hülsing and Patrick Weiden},
      title = {Discrete Ziggurat: A Time-Memory Trade-off for Sampling from a Gaussian Distribution over the Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2013/510},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/510}},
      url = {https://eprint.iacr.org/2013/510}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.