Added later: In retrospect, now I know a little more about cryptography, I can see that my confusion here is caused entirely by the fact that I didn’t know the meaning of the technical term “semantic security”.
Ever since Craig Gentry’s seminal work in 2009, there has been a certain amount of excitement about the potential of fully homomorphic encryption. The idea, I gather, is that using a fully homomorphic encryption scheme makes it possible to perform computations on encrypted data without decrypting it, yielding an encrypted result. For example, this would make it possible to process confidential data in an untrusted data centre.
The technology is edging towards practicality as better schemes are devised, and it may soon reach the point where it’s useful in some real-world situations.
But there’s something I don’t understand. I’m hoping that someone who does understand it may come across this and explain it.
The techniques used seem to allow the computation of arbitrary polynomials over various finite rings, and – at least in everything I’ve read – it’s always treated as obvious that this is equivalent to allowing arbitrary computations. Is that actually true? If so, is it really obvious? I’d love some enlightenment here.
A related source of confusion is that clearly any encryption scheme that actually supported arbitrary computations on encrypted values would be hopelessly insecure. For example, suppose you have encrypted a ten-character ascii password. I then run the function that extracts the first character. The result I get is still encrypted, but since there are only 128 possible values for an ascii character, I can encrypt each of these values and compare the result to the result of my computation. (I can do this because I can always encrypt any data of my choice, just by running a constant-valued function inside the encryption.) Then I do the same for the second character, and so on, till I have your complete password. Encryption fail!
The only reasonable conclusion I can draw from this is that fully homomorphic encryption does not really permit arbitrary computations on the encrypted data. In that case,
- Why do people keep saying it does?
- What is the class of computations that are in fact permitted? Is it just the evaluation of polynomials?
People of the Internet, I thank you.
Added later: After reading some more about it, I think Gentry’s scheme has the property that each plaintext can be represented by a large number of possible ciphertexts. This could potentially have the effect that the decoding scheme I described can’t be made to work. Is that relevant?