Paper 2010/088

An Efficient and Parallel Gaussian Sampler for Lattices

Chris Peikert


At the heart of many recent lattice-based cryptographic schemes is a polynomial-time algorithm that, given a `high-quality' basis, generates a lattice point according to a Gaussian-like distribution. Unlike most other operations in lattice-based cryptography, however, the known algorithm for this task (due to Gentry, Peikert, and Vaikuntanathan; STOC 2008) is rather inefficient, and is inherently sequential. We present a new Gaussian sampling algorithm for lattices that is \emph{efficient} and \emph{highly parallelizable}. We also show that in most cryptographic applications, the algorithm's efficiency comes at almost no cost in asymptotic security. At a high level, our algorithm resembles the ``perturbation'' heuristic proposed as part of NTRUSign (Hoffstein \etal, CT-RSA 2003), though the details are quite different. To our knowledge, this is the first algorithm and rigorous analysis demonstrating the security of a perturbation-like technique.

Available format(s)
Publication info
Published elsewhere. Full version of paper to appear in CRYPTO 2010
Lattice-based cryptographydiscrete Gaussian distribution
Contact author(s)
cpeikert @ cc gatech edu
2011-04-14: last of 2 revisions
2010-02-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chris Peikert},
      title = {An Efficient and Parallel Gaussian Sampler for Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2010/088},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.