Craig Gentry

Fully Homomorphic Encryption Using Ideal Lattices

Craig Gentry (To Appear...)

We propose a fully homomorphic encryption scheme - i.e., a scheme
that allows one to evaluate circuits over encrypted data without
being able to decrypt. Our solution comes in three steps. First, we
provide a general result - that, to construct an encryption scheme
that permits evaluation of arbitrary circuits, it suffices to
construct an encryption scheme that can evaluate (slightly augmented
 versions of) its own decryption circuit; we call a scheme that can
evaluate its (augmented) decryption circuit bootstrappable.

Next, we describe a public key encryption scheme using ideal
lattices that is almost bootstrappable. Lattice-based cryptosystems
typically have decryption algorithms with low circuit complexity,
often dominated by an inner product computation that is in NC1.
Also, ideal lattices provide both additive and multiplicative
homomorphisms (modulo a public-key ideal in a polynomial ring that
is represented as a lattice), as needed to evaluate general circuits.

Unfortunately, our initial scheme is not quite bootstrappable -
i.e., the depth that the scheme can correctly evaluate can be
logarithmic in the lattice dimension, just like the depth of the
decryption circuit, but the latter is greater than the former. In
the final step, we show how to modify the scheme to reduce the depth
 of the decryption circuit, and thereby obtain a bootstrappable
encryption scheme, without reducing the depth that the scheme can
evaluate. Abstractly, we accomplish this by enabling the encrypter
to start the decryption process, leaving less work for the
decrypter, much like the server leaves less work for the decrypter
in a server-aided cryptosystem.