Alice and Bob in Cipherspace
A new form of encryption allows you to compute with data you cannot read
The Pause That Refreshes
This is where the story gets wacky and wonderful. The evaluate function built into the cryptosystem is capable of performing any computation, provided it does not exceed the noise limit on circuit depth. So we can ask evaluate to run the decrypt function. Evaluate is designed to work with encrypted data, so the secret key supplied to it in this circumstance is an encrypted version of the normal key; specifically, the secret key supplied to decrypt running within evaluate is the ciphertext produced when encrypt is applied to the plaintext of the secret key. When decrypt is run with this enciphered key, the result is not plaintext but a new encryption of the ciphertext, with reduced noise.
In effect, Alice is giving Bob a copy of the key needed to unlock the data, but the key is inside a securely locked box and can only be used within that box. As a matter of fact, the box is locked with the very key that is locked inside the box! (Gentry discusses an even more elaborate version of this dizzying metaphor, in which Alice manufactures jewelry in the locked boxes.)
The pause to re-encrypt and refresh the noisy ciphertext can be repeated as needed. In this way the computer can handle a circuit of any finite depth, and the system becomes fully homomorphic. It can carry out arbitrarily complex computations on encrypted data.
An essential assumption in this scheme is that the decrypt circuit is itself shallow enough to run without exceeding the noise threshold. Indeed, its depth needs to be a little less than the limit, or else the computer will spend all its time refreshing the data and will never accomplish any useful work. When Gentry first formulated his FHE scheme, he found that this condition was not met. The evaluate function could not run the decrypt routine without accumulating excessive noise. The remedy was a technique for “squashing” decrypt, at the cost of making the key larger and more complicated. With this last innovation, the problem was solved.