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 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 Gentrys 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]. 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-ECbVPDSDgp

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 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/2633600
Publisher site
See Article on Publisher Site

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 Gentrys 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].

Journal

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

Published: Jul 1, 2014

Keywords: Fully homomorphic encryption

References

  • A sieve algorithm for the shortest lattice vector problem
    Ajtai, Miklós; Kumar, Ravi; Sivakumar, D.
  • Fast cryptographic primitives and circular-secure encryption based on hard learning problems
    Applebaum, Benny; Cash, David; Peikert, Chris; Sahai, Amit
  • Evaluating 2-DNF formulas on ciphertexts
    Boneh, Dan; Goh, Eu-Jin; Nissim, Kobbi
  • Fully homomorphic encryption without modulus switching from classical GapSVP
    Brakerski, Zvika
  • Fully homomorphic encryption from ring-LWE and security for key dependent messages
    Brakerski, Zvika; Vaikuntanathan, Vinod
  • Efficient fully homomorphic encryption from (standard) LWE
    Brakerski, Zvika; Vaikuntanathan, Vinod
  • Fully homomorphic encryption over the integers with shorter public keys
    Coron, Jean-Sébastien; Mandal, Avradip; Naccache, David; Tibouchi, Mehdi
  • A fully homomorphice encryption scheme
    Gentry, Craig
  • Fully homomorphic encryption using ideal lattices
    Gentry, Craig
  • Fully homomorphic encryption without squashing using depth-3 arithmetic circuits
    Gentry, Craig; Halevi, Shai
  • Implementing gentry’s fully-homomorphic encryption scheme
    Gentry, Craig; Halevi, Shai
  • Ring switching in BGV-style homomorphic encryption
    Gentry, Craig; Halevi, Shai; Peikert, Chris; Smart, Nigel P.
  • Better bootstrapping in fully homomorphic encryption
    Gentry, Craig; Halevi, Shai; Smart, Nigel P.
  • 2012c
    Gentry, Craig; Halevi, Shai; Smart, Nigel P.
  • 2012d
    Gentry, Craig; Halevi, Shai; Smart, Nigel P.
  • i-Hop homomorphic encryption and rerandomizable Yao circuits
    Gentry, Craig; Halevi, Shai; Vaikuntanathan, Vinod
  • Probabilistic encryption
    Goldwasser, Shafi; Micali, Silvio
  • HElib: An implementation of homomorphic encryption
    Halevi, Shai; Shoup, Victor
  • Evaluating branching programs on encrypted data
    Ishai, Yuval; Paskin, Anat
  • Can homomorphic encryption be practical? In Proceedings of the 3rd ACM Cloud Computing Security Workshop (CCSW’11)
    Lauter, Kristin; Naehrig, Michael; Vaikuntanathan, Vinod
  • On ideal lattices and learning with errors over rings
    Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded
  • Additively homomorphic encryption with d-operand multiplications
    Melchor, Carlos Aguilar; Gaborit, Philippe; Herranz, Javier
  • Generalized compact knapsacks, cyclic lattices, and efficient one-way functions
    Micciancio, Daniele
  • A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
    Micciancio, Daniele; Voulgaris, Panagiotis
  • Public-key cryptosystems from the worst-case shortest vector problem: Extended abstract
    Peikert, Chris
  • On lattices, learning with errors, random linear codes, and cryptography
    Regev, Oded
  • Oded Regev
    Regev, Oded
  • On data banks and privacy homomorphisms
    Rivest, Ron; Adleman, Leonard; Dertouzos, Michael L.
  • A hierarchy of polynomial time lattice basis reduction algorithms
    Schnorr, Claus-Peter
  • Fully homomorphic encryption with relatively small key and ciphertext sizes
    Smart, Nigel P.; Vercauteren, Frederik
  • Fully homomorphic SIMD operations
    Smart, Nigel P.; Vercauteren, Frederik
  • Faster fully homomorphic encryption
    Stehlé, Damien; Steinfeld, Ron
  • Fully homomorphic encryption over the integers
    van Dijk, Marten; Gentry, Craig; Halevi, Shai; Vaikuntanathan, Vinod