### Volume 2016

#### 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)