### An Efficient and Parallel Gaussian Sampler for Lattices

Chris Peikert

##### 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.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Full version of paper to appear in CRYPTO 2010
Keywords
Lattice-based cryptographydiscrete Gaussian distribution
Contact author(s)
cpeikert @ cc gatech edu
History
2011-04-14: last of 2 revisions
See all versions
Short URL
https://ia.cr/2010/088

CC BY

BibTeX

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