If e has this self-referential property of being able to
handle its own decryption function (augmented by a single
gate), we say that it is bootstrappable. As we will show, if e
is bootstrappable, then one can use e to construct a fully
homomorphic encryption scheme e †.
4. 3. Bootstrappable to fully homomorphic
Suppose that e is bootstrappable. In particular, suppose that
e can handle the following four functions: the decryption
function, expressed as a circuit De of size polynomial in l, as
well as De augmented by an Add, Sub, or Mult gate modulo 2.
(De augmented by Add consists of two copies of De connected
by an Add gate.) We will show that this is a complete set of circuits, in the sense that if these four circuits are in Fe, then one
can construct from e a scheme e † that is fully homomorphic.
As a warm-up, suppose that ciphertext c1 encrypts the bit
m under key pk1. Suppose also that we have an encrypted
secret key: let sk1 be a vector of ciphertexts that encrypt the
bits of sk1 under pk2 via Encrypte(pk2, sk1j). Consider the following algorithm.
recrypte(pk2, De, sk1, c1).
Generate c — 1 via Encrypte (pk2, c1j) over the bits of c1
Output c ¬ Evaluatee (pk2, De, sk1, c — 1 )
The decryption circuit De has input wires for the bits of a
secret key and the bits of a ciphertext. Above, Evaluatee takes
in the bits of sk1 and c1, each encrypted under pk2. Then, e is
used to evaluate the decryption circuit homomorphically. As
long as e can handle De, the output c is an encryption under
pk2 of Decrypte(sk1, c1) = m. recrypte therefore outputs a new
encryption of m, but under pk2.
One fascinating thing about recrypte is that the message m is doubly encrypted at one point, first under pk1
and next under pk2. Ordinarily, the only thing one can do
with a doubly encrypted message is to peel off the outer
encryption first, and then decrypt the inner layer. However,
in recrypte, the Evaluatee algorithm is used to remove the
inner encryption, just like Alice unlocks box i while it is
inside box #(i + 1).
It is also useful to imagine that e is our somewhat homomorphic encryption scheme from Section 3, and consider
what recrypte does to the noise of the ciphertexts. Evaluating
De removes the noise associated to the first ciphertext
under pk1 (because, of course, decryption removes noise),
but Evaluatee simultaneously introduces new noise while
evaluating the ciphertexts under pk2. As long as the new
noise added is less than the old noise removed, we have
made “progress.” A similar situation holds in Alice’s jewelry
store. When the worker extracts the piece from the used-up glovebox i, this process simultaneously uses up the
gloves of box #(i + 1). We have made “progress” as long as
the process does not leave box #(i + 1)’s gloves completely
Of course, our goal is to perform actual operations on
underlying messages, not merely to obtain a new encryption
of the same message. So, suppose that e can handle De augmented by some gate—e.g., Add; call this augmented circuit
DAdd. If c1 and c2 are two ciphertexts that encrypt m1 and m2,
102 CommunICAtIonS of the ACm | MArCh 2010 | VoL. 53 | no. 3
respectively, under pk1, and we compute c — 1 and c — 2 as before,
as ciphertexts encrypting the bits of the ciphertexts under
pk2, then we have that
c ¬ Evaluatee (pk2, DAdd, sk1, c — 1, c — 2 )
is an encryption under pk2 of m1 Å m2.
By recursing this process, we get a fully homomorphic encryption scheme. The public key in e† consists of
a sequence of public keys (pk1, …, pk+ 1) and a chain of
encrypted secret keys sk1, ..., sk, where ski is encrypted
under pki+ 1. To evaluate a function f in e†, we express f as
a circuit, topologically arrange its gates into levels, and
step through the levels sequentially. For a gate at level i + 1
(e.g., an Add gate), we take as input the encrypted secret key
ski and a couple of ciphertexts associated to output wires
at level i that are under pki, and we homomorphically evaluate DAdd to get a ciphertext under pki+ 1 associated to a wire at
level i + 1. Finally, we output the ciphertext associated to the
output wire of f.
Putting the encrypted secret key bits sk1, ..., sk in e†’s
public key is not a problem for security. These encrypted
secret-key bits are indistinguishable from encryptions of 0
as long as e is semantically secure.
4. 4. Circular security
Strictly speaking, e† does not quite meet our definition of
fully homomorphic encryption, since the complexity of
KeyGene† grows linearly with the maximum circuit depth we
want to evaluate. (Fortunately, Encrypte† and Decrypte† do
not depend at all on the function f being evaluated.)
However, suppose that e is not only bootstrappable, but
also circular-secure—that is, it is “safe” to reveal the encryption of a secret key ski under its own associated public key
pki. Then, we can simplify KeyGene†. We do not need distinct
public keys pki for each circuit level and an acyclic chain of
encrypted secret keys. Instead, the public key in e† can consist merely of a single public key pk and a single encrypted
secret key sk (sk under pk), where pk is associated to all levels of the circuit. This approach has the additional advantage that we do not need to decide beforehand the maximal
circuit depth complexity of the functions that we want to be
able to evaluate.
For most encryption schemes, including our somewhat homomorphic scheme (as far as we know), revealing
an encryption of sk under pk does not lead to any attack.
However, it is typically difficult to prove that an encryption
scheme is circular-secure.
The issue of circular security also fits within our physical
analogy. Suppose that a key is locked inside the very same
box that the key could open from the outside. Is it possible to
use the gloves and key to open the box from the inside If so, it
would be a strange lock. Similarly, encryption schemes that
are insecure in this setting tend to be contrived.
5. Some WhAt homomoRPhIC to
Is our somewhat homomorphic encryption scheme from
Section 3 already bootstrappable? Can it handle its own