Chicago Journal of Theoretical Computer Science

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


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.

Submitted October 1st, 2014, revised April 19, 2016, published June 8, 2016.

DOI: 10.4086/cjtcs.2016.007

[] Volume 2016, Article 6 [] Article 8
[back] Volume 2016 [back] Published articles
[CJCTS home]