Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

(Leveled) Fully Homomorphic Encryption without Bootstrapping

(Leveled) Fully Homomorphic Encryption without Bootstrapping (Leveled) Fully Homomorphic Encryption without Bootstrapping ZVIKA BRAKERSKI, Weizmann Institute of Science CRAIG GENTRY, IBM Research VINOD VAIKUNTANATHAN, MIT and University of Toronto 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 http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

(Leveled) Fully Homomorphic Encryption without Bootstrapping

Download PDF
36 pages

Loading next page...
 
/lp/association-for-computing-machinery/leveled-fully-homomorphic-encryption-without-bootstrapping-FMLcltVqkI

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Association for Computing Machinery
Copyright
Copyright © 2014 by ACM Inc.
ISSN
1942-3454
DOI
10.1145/2633600
Publisher site
See Article on Publisher Site

Abstract

(Leveled) Fully Homomorphic Encryption without Bootstrapping ZVIKA BRAKERSKI, Weizmann Institute of Science CRAIG GENTRY, IBM Research VINOD VAIKUNTANATHAN, MIT and University of Toronto 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

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Jul 1, 2014

There are no references for this article.