(Leveled) Fully Homomorphic Encryption without Bootstrapping

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…

• SF
  Simons Foundation
• DA
  Defense Advanced Research Projects Agency

  Awards: FA8750-11-2-0225, FA8750-11-C-0096
• NS
  Natural Sciences and Engineering Research Council of Canada