Cryptology ePrint Archive: Report 2010/088

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.

Category / Keywords: foundations / Lattice-based cryptography, discrete Gaussian distribution

Publication Info: Full version of paper to appear in CRYPTO 2010

Date: received 18 Feb 2010, last revised 13 Apr 2011

Contact author: cpeikert at cc gatech edu

Available format(s): PDF | BibTeX Citation

Version: 20110414:023411 (All versions of this report)

Short URL: ia.cr/2010/088

Discussion forum: Show discussion | Start new discussion