Volume 2016
Article 7
Published by the Department of Computer Science, The University of Chicago.
A Note on Discrete Gaussian Combinations of Lattice Vectors
Divesh Aggarwal
Department of Computer and Communication Sciences,
EFPL, Lausanne, Switzerland;
divesh.aggarwal AT epfl DOT ch
Oded Regev
Courant Institute of Mathematical Sciences,
New York University, New York, USA;
regev AT cims DOT nyu DOT edu
June 8, 2016
Abstract
We prove a local central limit theorem for the sum of one-dimensional discrete
Gaussians in $n$-dimensional space. In more detail, we analyze the distribution of
$\sum_{i=1}^m v_i \mathbf{x}_i$ where $\mathbf{x}_1,\ldots,\mathbf{x}_m$
are fixed vectors from some
lattice $\mathcal{L} \subset \mathbb{R}^n$ and $v_1,\ldots,v_m$ are chosen
independently from a
discrete Gaussian distribution over $\mathbb{Z}$. We show that under a
natural constraint
on $\mathbf{x}_1,\ldots,\mathbf{x}_m$, if the $v_i$ are chosen from a
wide enough Gaussian, the
sum is statistically close to a discrete Gaussian over $\mathcal{L}$.
We also analyze the
case of $\mathbf{x}_1,\ldots,\mathbf{x}_m$ that are themselves chosen from a
discrete Gaussian distribution (and fixed).
Our results simplify and qualitatively improve upon a recent result by Agrawal,
Gentry, Halevi, and Sahai.
- The article: PDF (233 KB)
- Source material: ZIP (156 KB)
- BibTeX entry for this
article (288 bytes)
Submitted October 1st, 2014, revised April 19, 2016, published June 8, 2016.
Volume 2016, Article 6
Article 8
Volume 2016
Published articles