An Efficient and Parallel Gaussian Sampler for Lattices

By Chris Peikert. Annual International Cryptology Conference, 2010

446 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/8c9f8dbb6af53f850f43db29f81197b1ed1ea93a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

Citations in the corpus

Lattice Signatures Without Trapdoors (2012, methodology): “This is mostly due to the constants that are hidden in the big-Oh notation of the trapdoor generation algorithms of [3] and [36].”
Pseudorandom Functions and Lattices (2012, methodology): “Fortunately, a suitable randomized rounding method does so [32].”
Classical hardness of learning with errors (2013, background): “Assume that Lemma 2.10 (Special case of [Pei10, Theorem 3.1]).”
Making NTRU as Secure as Worst-Case Problems over Ideal Lattices (2011, background): “Recently, Peikert [40] showed how to signi cantly improve on the e ciency of the Gaussian sampling algorithm from [10], in the case of q-ary lattices, and even further for module q-ary lattices.”
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller (2012, methodology): “In particular, we give the first parallel algorithm for inverting gA under asymptotically optimal error rates (previously, handling such large errors required the sequential “nearest-plane” algorithm of [7]), and our preimage sampling algorithm for fA works with smaller integers and requires much le”
Bonsai Trees, or How to Delegate a Lattice Basis (2010, background): “For Item 5 above, a recent work [46] gives an alternative SampleD algorithm that is more efficient and fully parallelizable; it works for any s ≥ σ1(S) · ω( √ log n), where σ1(S) is the largest singular value of S (which is never less than ‖ ̃ S‖, but is also not much larger in most important cases;”
Hardness of SIS and LWE with Small Parameters (2013, background): “3), which strengthens similar ones previously proved in [22, 6].”
Better Key Sizes (and Attacks) for LWE-Based Encryption (2011, methodology): “The security proof combines a number of techniques and perspectives from recent works [25, 21, 29 ] for the purpose of improved efficiency and a tight analysis.”
The Discrete Gaussian for Differential Privacy (2020, background): “This is the natural discrete analogue of the continuous Gaussian (which has density (1/ √ 2πσ2) · e−(x−μ) (2)/2σ(2) at x ∈ R), and it arises in lattice-based cryptography (in a multivariate form, which is believed to be hard to sample from) [GPV08; Reg09; Pei10; Ste17, etc.].”
Discrete Gaussian Leftover Hash Lemma over Infinite Domains (2013, methodology): “Such samplers, that sample from a spherical discrete Gaussian distribution over a lattice have been constructed by [GPV08] (using an algorithm by Klein [Kle00]) as well as Peikert [Pei10].”