Welcome to the resource topic for 2010/088
Title:
An Efficient and Parallel Gaussian Sampler for Lattices
Authors: 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.
ePrint: https://eprint.iacr.org/2010/088
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .