A note on discrete gaussian combinations of lattice vectors

Divesh Aggarwal, Oded Regev

Research output: Contribution to journalArticle

Abstract

We analyze the distribution of $\sum_{i=1}^m v_i \bx_i$ where $\bx_1,...,\bx_m$ are fixed vectors from some lattice $\cL \subset \R^n$ (say $\Z^n$) and $v_1,...,v_m$ are chosen independently from a discrete Gaussian distribution over $\Z$. We show that under a natural constraint on $\bx_1,...,\bx_m$, if the $v_i$ are chosen from a wide enough Gaussian, the sum is statistically close to a discrete Gaussian over $\cL$. We also analyze the case of $\bx_1,...,\bx_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 \cite{AGHS13}.
Original languageUndefined
Article number1308.2405
JournalarXiv
StatePublished - Aug 11 2013

Keywords

  • cs.CR
  • math.CO
  • math.PR

Cite this