CryptoDB
An Efficient and Parallel Gaussian Sampler for Lattices
Authors: | |
---|---|
Download: | |
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 }