(Leveled) Fully Homomorphic Encryption without Bootstrapping

Abstract

We present a novel approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled, fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits of a-priori bounded depth), without Gentry’s bootstrapping procedure.

Specifically, we offer a choice of FHE schemes based on the learning with error (LWE) or Ring LWE (RLWE) problems that have 2 λ security against known attacks. We construct the following.

(1) A leveled FHE scheme that can evaluate depth-L arithmetic circuits (composed of fan-in 2 gates) using O(λ. L3) per-gate computation, quasilinear in the security parameter. Security is based on RLWE for an approximation factor exponential in L. This construction does not use the bootstrapping procedure.

(2) A leveled FHE scheme that can evaluate depth-L arithmetic circuits (composed of fan-in 2 gates) using O(λ2) per-gate computation, which is independent of L. Security is based on RLWE for quasipolynomial factors. This construction uses bootstrapping as an optimization.

We obtain similar results for LWE, but with worse performance. All previous (leveled) FHE schemes required a per-gate computation of Ω(λ3.5), and all of them relied on subexponential hardness assumptions.

We introduce a number of further optimizations to our scheme based on the Ring LWE assumption. As an example, for circuits of large width (e.g., where a constant fraction of levels have width Ω(λ)), we can reduce the per-gate computation of the bootstrapped version to O(λ), independent of L, by batching the bootstrapping operation. At the core of our construction is a new approach for managing the noise in lattice-based ciphertexts, significantly extending the techniques of Brakerski and Vaikuntanathan [2011b].

References

1. Miklós Ajtai, Ravi Kumar, and D. Sivakumar. 2001. A sieve algorithm for the shortest lattice vector problem. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC’01). ACM, 601--610.
2. Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. 2009. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In Proceedings of the 29th Annual International Cryptology Conference (CRYPTO’09). Lecture Notes in Computer Science, vol. 5677, Springer, Berlin, 595--618.
3. Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. 2005. Evaluating 2-DNF formulas on ciphertexts. In Proceedings of the 2nd Theory of Cryptography Conference (TCC’05). Lecture Notes in Computer Science, vol. 3378, Springer, Berlin, 325--342.
4. Zvika Brakerski. 2012. Fully homomorphic encryption without modulus switching from classical GapSVP. In Proceedings of the 32nd Annual Cryptology Conference (CRYPTO’12). Lecture Notes in Computer Science, vol. 7417, Springer, Berlin, 868--886.
5. Zvika Brakerski and Vinod Vaikuntanathan. 2011a. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In Proceedings of the 31st Annual Cryptology Conference (CRYPTO’11). Lecture Notes in Computer Science, vol. 6841, Springer, Berlin, 505--524.
6. Zvika Brakerski and Vinod Vaikuntanathan. 2011b. Efficient fully homomorphic encryption from (standard) LWE. In Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS’11). IEEE, 97--106.
7. Jean-Sébastien Coron, Avradip Mandal, David Naccache, and Mehdi Tibouchi. 2011. Fully homomorphic encryption over the integers with shorter public keys. In Proceedings of the 31st Annual Cryptology Conference (CRYPTO’11), Phillip Rogaway Ed., Lecture Notes in Computer Science, vol. 6841, Springer, Berlin, 487--504.
8. Craig Gentry. 2009a. A fully homomorphice encryption scheme. Ph.D. dissertation, Stanford University, Stanford, CA. crypto.stanford.edu/craig.
9. Craig Gentry. 2009b. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC’09). Michael Mitzenmacher Ed., ACM, 169--178.
10. Craig Gentry and Shai Halevi. 2011a. Fully homomorphic encryption without squashing using depth-3 arithmetic circuits. In Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS’11). Rafail Ostrovsky Ed., IEEE, 107--109.
11. Craig Gentry and Shai Halevi. 2011b. Implementing gentry’s fully-homomorphic encryption scheme. In Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’11). Lecture Notes in Computer Science, vol. 6632, Springer, Berlin, 29--148.
12. Craig Gentry, Shai Halevi, Chris Peikert, and Nigel P. Smart. 2012a. Ring switching in BGV-style homomorphic encryption. In Proceedings of the 8th International Conference on Security and Cryptography for Networks (SCN’12). Ivan Visconti and Roberto De Prisco Eds., Lecture Notes in Computer Science, vol. 7485, Springer, Berlin, 19--37.
13. Craig Gentry, Shai Halevi, and Nigel P. Smart. 2012b. Better bootstrapping in fully homomorphic encryption. In Proceedings of the 15th International Conference on Practice and Theory in Public Key Cryptography (PKC’12). Marc Fischlin, Johannes Buchmann, and Mark Manulis Eds., Lecture Notes in Computer Science, vol. 7293, Springer, Berlin, 1--16.
14. Craig Gentry, Shai Halevi, and Nigel P. Smart. 2012c. Fully homomorphic encryption with polylog overhead. In Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’12). David Pointcheval and Thomas Johansson Eds., Lecture Notes in Computer Science, vol. 7237, Springer, Berlin, 465--482.
15. Craig Gentry, Shai Halevi, and Nigel P. Smart. 2012d. Homomorphic evaluation of the AES circuit. In Proceedings of the 32nd Annual Cryptology Conference (CRYPTO’12). Reihaneh Safavi-Naini and Ran Canetti Eds., Lecture Notes in Computer Science, vol. 7417, Springer, Berlin, 850--867.
16. Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. 2010. i-Hop homomorphic encryption and rerandomizable Yao circuits. In Proceedings of the 30th Annual Cryptology Conference (CRYPTO’10). Lecture Notes in Computer Science, vol. 6223, Springer, Berlin, 155--172.
17. Shafi Goldwasser and Silvio Micali. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2, 270--299.
18. Shai Halevi and Victor Shoup. 2013. HElib: An implementation of homomorphic encryption. https://github.com/shaih/HElib.
19. Yuval Ishai and Anat Paskin. 2007. Evaluating branching programs on encrypted data. In Proceedings of the 4th Theory of Cryptography Conference (TCC’07). Salil P. Vadhan Ed., Lecture Notes in Computer Science, vol. 4392, Springer, Berlin, 575--594.
20. Kristin Lauter, Michael Naehrig, and Vinod Vaikuntanathan. 2011. Can homomorphic encryption be practical? In Proceedings of the 3rd ACM Cloud Computing Security Workshop (CCSW’11). ACM, 113--124.
21. Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2010. On ideal lattices and learning with errors over rings. In Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’10). Lecture Notes in Computer Science, vol. 6110, Springer, Berlin, 1--23.
22. Carlos Aguilar Melchor, Philippe Gaborit, and Javier Herranz. 2010. Additively homomorphic encryption with d-operand multiplications. In Proceedings of the 30th Annual Cryptology Conference (CRYPTO’10). Tal Rabin Ed., Lecture Notes in Computer Science, vol. 6223, Springer, Berlin, 138--154.
23. Daniele Micciancio. 2007. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computat. Complex. 16, 4, 365--411.
24. Daniele Micciancio and Panagiotis Voulgaris. 2010. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC’10). Leonard J. Schulman Ed., ACM, 351--358.
25. Chris Peikert. 2009. Public-key cryptosystems from the worst-case shortest vector problem: Extended abstract. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC’09). ACM, 333--342.
26. Oded Regev. 2005. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC’05). Harold N. Gabow and Ronald Fagin Eds., ACM, 84--93.
27. Oded Regev. 2010. Oded Regev. 2010. The learning with errors problem (invited survey). In Proceedings of the IEEE Conference on Computational Complexity (CCC’10). IEEE Computer Society, 191--204.
28. Ron Rivest, Leonard Adleman, and Michael L. Dertouzos. 1978. On data banks and privacy homomorphisms. In Foundations of Secure Computation. Academic Press, Inc., Orlando, FL, 169--180.
29. Claus-Peter Schnorr. 1987. A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53, 201--224.
30. Nigel P. Smart and Frederik Vercauteren. 2010. Fully homomorphic encryption with relatively small key and ciphertext sizes. In Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography (PKC’10). Lecture Notes in Computer Science, vol. 6056, Springer, Berlin, 420--443.
31. Nigel P. Smart and Frederik Vercauteren. 2011. Fully homomorphic SIMD operations. IACR Cryptol. ePrint Archive 2011, 133.
32. Damien Stehlé and Ron Steinfeld. 2010. Faster fully homomorphic encryption. In Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’10). Lecture Notes of Computer Science, vol. 6477, Springer, Berlin, 377--394.
33. Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. 2010. Fully homomorphic encryption over the integers. In Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’10). Lecture Notes in Computer Science, vol. 6110, Springer, Berlin, 24--43.

Index Terms

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques

      • Public key encryption