International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

An Efficient and Parallel Gaussian Sampler for Lattices

Authors:
Chris Peikert
Download:
URL: http://eprint.iacr.org/2010/088
Search ePrint
Search Google
Abstract: 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.
BibTeX
@misc{eprint-2010-22989,
  title={An Efficient and Parallel Gaussian Sampler for Lattices},
  booktitle={IACR Eprint archive},
  keywords={foundations / Lattice-based cryptography, discrete Gaussian distribution},
  url={http://eprint.iacr.org/2010/088},
  note={Full version of paper to appear in CRYPTO 2010 cpeikert@cc.gatech.edu 14747 received 18 Feb 2010, last revised 17 May 2010},
  author={Chris Peikert},
  year=2010
}