Abstract
We describe two improvements to Gentry’s fully homomorphic scheme based on ideal lattices and its analysis: we provide a more aggressive analysis of one of the hardness assumptions (the one related to the Sparse Subset Sum Problem) and we introduce a probabilistic decryption algorithm that can be implemented with an algebraic circuit of low multiplicative degree. Combined together, these improvements lead to a faster fully homomorphic scheme, with a Õ(λ 3.5) bit complexity per elementary binary add/mult gate, where λ is the security parameter. These improvements also apply to the fully homomorphic schemes of Smart and Vercauteren [PKC’2010] and van Dijk et al. [Eurocrypt’2010].
Chapter PDF
Similar content being viewed by others
References
Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6, 1–13 (1986)
Boyar, J., Peralta, R., Pochuev, D.: On the multiplicative complexity of boolean functions over the basis ( ∧ , ⊕ , 1). Theoret. Comput. Sci. 235(1), 43–57 (2000)
Cantor, D.G., Kaltofen, E.: On fast multiplication of polynomials over arbitrary algebras. Acta Inf. 28(7), 693–701 (1991)
Cassels, J.W.S.: An Introduction to the Geometry of Numbers, 2nd edn. Springer, Heidelberg (1971)
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)
Gama, N., Nguyen, P.Q.: Finding short lattice vectors within Mordell’s inequality. In: Proc. of STOC, pp. 207–216. ACM, New York (2008)
Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008)
Gentry, C.: A fully homomorphic encryption scheme. PhD thesis, Stanford University (2009), http://crypto.stanford.edu/craig (manuscript)
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proc. of STOC, pp. 169–178. ACM, New York (2009)
Gentry, C.: Computing arbitrary functions of encrypted data. Communications of the ACM 53(3), 97–105 (2010)
Gentry, C.: Toward basing fully homomorphic encryption on worst-case hardness. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 116–137. Springer, Heidelberg (2010)
Gentry, C., Halevi, S.: Implementing Gentry’s fully-homomorphic encryption scheme. Preliminary version (August 5, 2010), http://researcher.ibm.com/researcher/files/us-shaih/fhe-implementation.pdf
Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301), 13–30 (1963)
Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proc. of STOC, pp. 99–108. ACM, New York (1983)
Karp, R.M.: A survey of parallel algorithms for shared-memory machines. Technical report (1988)
Klein, P.N.: Finding the closest lattice vector when it’s unusually close. In: Proc. of SODA, pp. 937–941. ACM, New York (2000)
Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)
Ludwig, C.: A faster lattice reduction method using quantum search. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 199–208. Springer, Heidelberg (2003)
Micciancio, D.: Improving lattice-based cryptosystems using the Hermite normal form. In: Silverman, J.H. (ed.) CALC 2001. LNCS, vol. 2146, pp. 126–145. Springer, Heidelberg (2001)
Micciancio, D., Goldwasser, S.: Complexity of lattice problems: a cryptographic perspective. Kluwer Academic Press, Dordrecht (2002)
Micciancio, D., Regev, O.: Lattice-based Cryptography. In: Post-Quantum Cryptography. Springer, Heidelberg (2008)
Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: Proc. of STOC, pp. 351–358. ACM, New York (2010)
Nguyen, P.Q., Shparlinski, I.: On the insecurity of a server-aided RSA protocol. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 21–35. Springer, Heidelberg (2001)
Schnorr, C.P.: A hierarchy of polynomial lattice basis reduction algorithms. Theoret. Comput. Sci. 53, 201–224 (1987)
Schönhage, A., Strassen, V.: Schnelle Multiplikation grosser Zahlen. Computing 7, 281–292 (1971)
Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420–443. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 International Association for Cryptologic Research
About this paper
Cite this paper
Stehlé, D., Steinfeld, R. (2010). Faster Fully Homomorphic Encryption. In: Abe, M. (eds) Advances in Cryptology - ASIACRYPT 2010. ASIACRYPT 2010. Lecture Notes in Computer Science, vol 6477. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17373-8_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-17373-8_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17372-1
Online ISBN: 978-3-642-17373-8
eBook Packages: Computer ScienceComputer Science (R0)