(Leveled) Fully Homomorphic Encryption without Bootstrapping
ACM Transactions on Computation Theory · 2014-07 · 6 (3) · 1-36
DOI: 10.1145/2633600 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2014-07. Verfasst von Zvika Brakerski und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1303-mal zitiert (Crossref) und nennt 32 Literaturangaben. Gefördert von: Defense Advanced Research Projects Agency, Simons Foundation, Natural Sciences and Engineering Research Council of Canada.
Abstract (Originalsprache)
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].
Förderung
- Defense Advanced Research Projects Agency
- Simons Foundation
- Natural Sciences and Engineering Research Council of Canada
Zitieren
APA
Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2014). (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Transactions on Computation Theory, 6(3), 1-36. https://doi.org/10.1145/2633600
Vancouver
Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Transactions on Computation Theory. 2014;6(3):1-36. doi:10.1145/2633600
BibTeX
@article{Brakerski2014,
author = {Brakerski, Zvika and Gentry, Craig and Vaikuntanathan, Vinod},
title = {(Leveled) Fully Homomorphic Encryption without Bootstrapping},
journal = {ACM Transactions on Computation Theory},
year = {2014},
volume = {6},
number = {3},
pages = {1--36},
doi = {10.1145/2633600}
}
EUVIMED