Gentry’s homomorphic encryption
There's been a lot of talk lately about Craig Gentry's new homomorphic encryption scheme that’s based on lattice cryptography. The discussion that I've heard has been essentially one of two types. Some people are saying, "Wow, that's incredibly cool. And his proof is cool too." Others are saying, "What the heck is homomorphic encryption, anyway?" What follows is for the people who are saying the latter of these two.
The term "homomorphic" is used in homomorphic encryption because of the connection to a homomorphism, which is a function that roughly lets us switch the order of doing a mathematical operation and evaluating the function.
For an example of this, consider the function f(x) = ex. This function has the property that ex+y = exey, or that f(x + y) = f(x) * f(y), which means that we can roughly switch the order of implementing the mathematical operations and applying the function. In the first case, we apply the operation + first and then the function f, and that's equal to what we get from applying the function f first and then the operation *. A function that behaves that way is called a "homomorphism."
Now suppose that f is an encryption function that happens to be a homomorphism. If that's the case, you could implement an operation on plaintext by doing a different operation on ciphertext, and you could even do this without having to decrypt the ciphertext. From the point of view of most uses, this is a bad property because it lets an adversary change a ciphertext into one that decrypts into an entirely different plaintext, but that doesn't stop such functions from being inherently interesting.
If we have an RSA public key (n,e) and encrypt a message m by calculating c(m) = me mod n, then we have that c(xy) = (xy)e = xeye = c(x)c(y). This means that we can switch the order of encryption and multiplication and get the same result, so RSA is a form of homomorphic encryption. We can take advantage of this fact, for example, by changing a ciphertext c(x) into one that decrypts into 2x by multiplying c(x) by c(2), and we can do this without decrypting the ciphertext c(x).
On the other hand, this only works for multiplication and doesn't work for addition. For RSA encryption, we don't have that c(x + y) = c(x) + c(y). If we had that, we could do even more tricks with ciphertext and have something useful happen to the plaintext.
The reason that Gentry's work is interesting is that it lets you do just that. It's homomorphic for both addition and multiplication. His scheme lets you do an arbitrary number of additions and multiplications, with the only requirement being that a limit on the number of multiplications needs to be fixed when you generate a user's public key.
It also appears that Gentry's scheme is totally impractical. This means that we won't be seeing a start-up that makes products based on Gentry's homomorphic encryption scheme any time soon, but that shouldn't stop us from admiring the elegance of his invention.