An Efficient and Parallel Gaussian Sampler for Lattices

Chris Peikert

Crypto 2010

Time bound

O(n²) online real operations; O(n²/P) per processor

Space bound

Offline matrices and fresh perturbation vector

Source / version date

2010

Comparison variant

Classical · supplied basis · parallel online

Cost scale

Online arithmetic operations

Width / covariance

Covariance Sigma > r^2 B B^T, r=omega(sqrt(log n)); spherical sufficient condition s > r s_1(B)

Offline preparation

Matrix factorization/inversion and one fresh continuous-Gaussian perturbation before each query

Output

One sample on L+c, arbitrary real shift c

Distribution error

Negligible statistical distance

Online model

Theorem 4.2: P <= n^2 processors; O(n^2/P) sufficiently precise real operations per processor

Assumptions and source notes

The scalar width is controlled by the largest singular value, not the longest Gram–Schmidt vector. Publication year is known; the detailed theorem was checked in the 2011 full author version.

Source location

Algorithm 1 and Theorem 4.2, printed pp. 11–12
Version: CRYPTO 2010 paper; checked full author version dated 13 April 2011

Primary source ↗

@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}
}