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 \(\{\vec x_i\}_{i=1}^m\) from some lattice L ⊂ ℝn, we analyze the probability distribution \(\sum_{i=1}^m z_i \vec x_i\) where the integer vector \(\vec z \in \mathbb{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 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 \(\vec x_i\)’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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agrawal, S., Gentry, C., Halevi, S., Sahai, A.: Discrete gaussian leftover hash lemma over infinite domains (2012), http://eprint.iacr.org/2012/714
Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen 296(4), 625–635 (1993)
Boneh, D., Freeman, D.M.: Homomorphic signatures for polynomial functions. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 149–168. Springer, Heidelberg (2011)
Ducas, L., Nguyen, P.Q.: Learning a zonotope and more: Cryptanalysis of ntrusign countermeasures. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 433–450. Springer, Heidelberg (2012)
Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices and applications. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013), http://eprint.iacr.org/2013/610
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Dwork, C. (ed.) STOC, pp. 197–206. ACM (2008)
Klein, P.: Finding the closest lattice vector when it’s unusually close. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000, pp. 937–941 (2000)
Litvak, A.E., Pajor, A., Rudelson, M., Tomczak-Jaegermann, N.: Smallest singular value of random matrices and geometry of random polytopes. Advances in Mathematics 195(2) (2005)
Lyubashevsky, V.: Lattice signatures without trapdoors. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 738–755. Springer, Heidelberg (2012)
Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. SIAM J. Computing 37(1), 267–302 (2007)
Nguyen, P.Q., Regev, O.: Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. J. Cryptol. 22(2), 139–160 (2009)
Peikert, C.: Limits on the hardness of lattice problems in l p norms. Computational Complexity 17(2), 300–351 (2008)
Peikert, C.: An efficient and parallel gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 80–97. Springer, Heidelberg (2010)
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. JACM 56(6) (2009)
Rothblum, R.: Homomorphic encryption: From private-key to public-key. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 219–234. Springer, Heidelberg (2011)
Rudelson, M., Vershynin, R.: Non-asymptotic theory of random matrices: extreme singular values. In: International Congress of Mathematicans (2010)
Tao, T.: Topics in random matrix theory. Graduate Studies in Mathematics, vol. 132. American Mathematical Society (2012)
van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully Homomorphic Encryption over the Integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Agrawal, S., Gentry, C., Halevi, S., Sahai, A. (2013). Discrete Gaussian Leftover Hash Lemma over Infinite Domains. In: Sako, K., Sarkar, P. (eds) Advances in Cryptology - ASIACRYPT 2013. ASIACRYPT 2013. Lecture Notes in Computer Science, vol 8269. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-42033-7_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-42033-7_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-42032-0
Online ISBN: 978-3-642-42033-7
eBook Packages: Computer ScienceComputer Science (R0)