## CryptoDB

### Paper: An Efficient and Parallel Gaussian Sampler for Lattices

Authors: Chris Peikert URL: http://eprint.iacr.org/2010/088 Search ePrint Search Google 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
}
`