Paper 2012/714
Discrete Gaussian Leftover Hash Lemma over Infinite Domains
Shweta Agrawal, Craig Gentry, Shai Halevi, and Amit Sahai
Abstract
The classic Leftover Hash Lemma (LHL) is one of the most useful tools in cryptography, and is often used to argue that certain distributions arising from modular subsetsums are close to uniform over some finite domain. Though extremely useful and powerful in general, the applicability of the leftover hash lemma to lattice based cryptography is limited for two reasons. First, typically the distributions we care about in latticebased cryptography are {\em discrete Gaussians}, not uniform. Second, the elements chosen from these discrete Gaussian distributions lie in an infinite domain: a lattice rather than a finite field. In this work we prove a ``lattice world" analog of LHL over infinite domains, proving that certain ``generalized subset sum'' distributions are statistically close to well behaved discrete Gaussian distributions, even without any modular reduction. Specifically, given many vectors $\{\vec x_i\}_{i=1}^m$ from some lattice $L\subset\R^n$, we analyze the probability distribution $\sum_{i=1}^m z_i \vec x_i$ where the integer vector $\vec z \in \Z^m$ is chosen from a discrete Gaussian distribution. We show that when the $\vec x_i$'s are ``random enough'' and the Gaussian from which the $\vec z$'s are chosen is ``wide enough'', then the resulting distribution is statistically close to a nearspherical discrete Gaussian over the lattice $L$. Beyond being interesting in its own right, this ``latticeworld" analog of LHL has applications for the new construction of multilinear maps \cite{GGH12}, where it is used to sample Discrete Gaussians obliviously. Specifically, given encoding of the $\vec x_i$'s, it is used to produce an encoding of a nearspherical Gaussian distribution over the lattice. We believe that our new lemma will have other applications, and sketch some plausible ones in this work.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 leftover hash lemmadiscrete gaussiansmultilinear maps
 Contact author(s)
 shweta a @ gmail com
 History
 20130322: revised
 20121227: received
 See all versions
 Short URL
 https://ia.cr/2012/714
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/714, author = {Shweta Agrawal and Craig Gentry and Shai Halevi and Amit Sahai}, title = {Discrete Gaussian Leftover Hash Lemma over Infinite Domains}, howpublished = {Cryptology ePrint Archive, Paper 2012/714}, year = {2012}, note = {\url{https://eprint.iacr.org/2012/714}}, url = {https://eprint.iacr.org/2012/714} }