Paper Info
Title
Discrete Gaussian Leftover Hash Lemma over Infinite Domains
Abstract
The classic Leftover Hash Lemma LHL is often used to argue that certain distributions arising from modular subset-sums are close to uniform over their finite domain. Though very powerful, the applicability of the leftover hash lemma to lattice based cryptography is limited for two reasons. First, typically the distributions we care about in lattice-based cryptography are 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 <InlineEquation ID=\"IEq1\" <EquationSource Format=\"TEX\"$\\{\\vec x_i\\}_{i=1}^m$</EquationSource> </InlineEquation> from some lattice L﾿﾿﾿ℝ n , we analyze the probability distribution <InlineEquation ID=\"IEq2\" <EquationSource Format=\"TEX\"$\\sum_{i=1}^m z_i \\vec x_i$</EquationSource> </InlineEquation> where the integer vector <InlineEquation ID=\"IEq3\" <EquationSource Format=\"TEX\"$\\vec z \\in \\mathbb{Z}^m$</EquationSource> </InlineEquation> is chosen from a discrete Gaussian distribution. We show that when the <InlineEquation ID=\"IEq4\" <EquationSource Format=\"TEX\"$\\vec x_i$</EquationSource> </InlineEquation>'s are \"random enough\" and the Gaussian from which the <InlineEquation ID=\"IEq5\" <EquationSource Format=\"TEX\"$\\vec z$</EquationSource> </InlineEquation>'s are chosen is \"wide enough\", then the resulting distribution is statistically close to a near-spherical discrete Gaussian over the lattice﾿L. Beyond being interesting in its own right, this \"lattice-world\" analog of LHL has applications for the new construction of multilinear maps [5], where it is used to sample Discrete Gaussians obliviously. Specifically, given encoding of the <InlineEquation ID=\"IEq6\" <EquationSource Format=\"TEX\"$\\vec x_i$</EquationSource> </InlineEquation>'s, it is used to produce an encoding of a near-spherical Gaussian distribution over the lattice. We believe that our new lemma will have other applications, and sketch some plausible ones in this work.
Year
DOI
Venue
2013
10.1007/978-3-642-42033-7_6
ASIACRYPT
Field
DocType
Volume
Probability mass function,Discrete mathematics,Combinatorics,Subset sum problem,Finite field,Leftover hash lemma,Probability distribution,Gaussian,Lattice-based cryptography,Mathematics,Lemma (mathematics)
Conference
8269
ISSN
Citations 
PageRank 
0302-9743
11
0.88
References 
Authors
11
4
Name
Order
Citations
PageRank
Shweta Agrawal163631.83
Craig Gentry29520380.03
Shai Halevi37203442.70
Amit Sahai413566545.52