DGS / Classical · q-ary supplied basis · online

An Efficient and Parallel Gaussian Sampler for Lattices

Chris Peikert

Crypto 2010

PublishedSource checked

Time bound: O(n²) integer operations plus n randomized-rounding calls online
Space bound: O(n² log q) matrix bits plus O(n log q) bits per fresh perturbation

Source / version date: 2010
Comparison variant: Classical · q-ary supplied basis · online
Cost scale: Online integer operations
Width requirement: s >= r(2 s_1(B)+1), r=omega(sqrt(log n)), for spherical covariance
Offline preparation: Precompute inverse and perturbations; a fresh perturbation is consumed for each output
Output: One sample on L+c; q Z^n contained in L contained in Z^n and c integral
Distribution error: Negligible statistical distance
Online model: P <= n^2 processors: O(n^2/P) integer operations and ceil(n/P) rounding calls each; arithmetic can be modulo q or q^2

Assumptions and source notes

The integer arithmetic bound excludes offline preparation and fresh perturbation generation. It uses the stronger operator-norm width promise.

Source location

§1.2; Algorithm 2 and Theorem 4.3, printed pp. 12–14
Version: CRYPTO 2010; full author version 13 April 2011

Selected earlier references

Selected sources cited by this paper.

Trapdoors for Hard Lattices and New Cryptographic Constructions
Craig Gentry · Chris Peikert · Vinod Vaikuntanathan · 2008
Replaces the sequential sampler with a parallel offline/online construction under an operator-norm width condition. Abstract; §1; references

Primary source ↗

BibTeXDownload .bib

@inproceedings{peikert-2010-gaussian,
  author = {Chris Peikert},
  title = {{An Efficient and Parallel Gaussian Sampler for Lattices}},
  booktitle = {Advances in Cryptology -- CRYPTO 2010},
  year = {2010},
  pages = {80--97},
  doi = {10.1007/978-3-642-14623-7_5},
  url = {https://doi.org/10.1007/978-3-642-14623-7_5},
  cr_date = {2010-12-31},
  cr_status = {published},
  cr_venue = {Advances in Cryptology -- CRYPTO 2010},
  cr_author_ids = {chris-peikert}
}