Communications - March 2010

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 used-up.

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.