(Leveled) Fully Homomorphic Encryption without Bootstrapping
Top Cited Papers
- 1 July 2014
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 6 (3), 1-36
- https://doi.org/10.1145/2633600
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 ( λ . L 3) 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].Keywords
Funding Information
- Defense Advanced Research Projects Agency (FA8750-11-C-0096, FA8750-11-2-0225)
- Simons Foundation
- Natural Sciences and Engineering Research Council of Canada
This publication has 23 references indexed in Scilit:
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVPLecture Notes in Computer Science, 2012
- Homomorphic Evaluation of the AES CircuitLecture Notes in Computer Science, 2012
- Fully Homomorphic Encryption over the IntegersLecture Notes in Computer Science, 2010
- On Ideal Lattices and Learning with Errors over RingsLecture Notes in Computer Science, 2010
- Fully Homomorphic Encryption with Relatively Small Key and Ciphertext SizesLecture Notes in Computer Science, 2010
- Faster Fully Homomorphic EncryptionLecture Notes in Computer Science, 2010
- Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning ProblemsLecture Notes in Computer Science, 2009
- Evaluating 2-DNF Formulas on CiphertextsLecture Notes in Computer Science, 2005
- A hierarchy of polynomial time lattice basis reduction algorithmsTheoretical Computer Science, 1987
- Probabilistic encryptionJournal of Computer and System Sciences, 1984