Paper 2011/279
Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits
Craig Gentry and Shai Halevi
Abstract
We describe a new approach for constructing fully homomorphic encryption (FHE) schemes. Previous FHE schemes all use the same blueprint from [Gentry 2009]: First construct a somewhat homomorphic encryption (SWHE) scheme, next "squash" the decryption circuit until it is simple enough to be handled within the homomorphic capacity of the SWHE scheme, and finally "bootstrap" to get a FHE scheme. In all existing schemes, the squashing technique induces an additional assumption: that the sparse subset sum problem (SSSP) is hard.
Our new approach constructs FHE as a hybrid of a SWHE and a multiplicatively homomorphic encryption (MHE) scheme, such as Elgamal. Our construction eliminates the need for the squashing step, and thereby also removes the need to assume the SSSP is hard. We describe a few concrete instantiations of the new method, including a "simple" FHE scheme where we replace SSSP with Decision Diffie-Hellman, an optimization of the simple scheme that let us "compress" the FHE ciphertext into a single Elgamal ciphertext(!), and a scheme whose security can be (quantumly) reduced to the approximate ideal-SIVP.
We stress that the new approach still relies on bootstrapping, but it shows how to bootstrap without having to "squash" the decryption circuit. The main technique is to express the decryption function of SWHE schemes as a depth-3 (
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Extended abstract in FOCS 2011, this is the full version
- Keywords
- Fully-homomorphic encryption
- Contact author(s)
- shaih @ alum mit edu
- History
- 2011-09-14: revised
- 2011-05-30: received
- See all versions
- Short URL
- https://ia.cr/2011/279
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2011/279, author = {Craig Gentry and Shai Halevi}, title = {Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits}, howpublished = {Cryptology {ePrint} Archive, Paper 2011/279}, year = {2011}, url = {https://eprint.iacr.org/2011/279} }