Something I don’t understand about homomorphic encryption

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,

  1. Why do people keep saying it does?
  2. 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?

This entry was posted in algorithms, chatter. Bookmark the permalink.

6 Responses to Something I don’t understand about homomorphic encryption

  1. davidcash says:

    Your “added later” comment nails it.

    A basic property of a secure encryption scheme (homomorphic or not) is: “Given a ciphertext C and message M, you shouldn’t be able to check if C is an encryption of M.”

    Gentry’s scheme has this property, as well as every other “modern” public-key encryption scheme. For most settings, this means that the encryption algorithm must be randomized in order to prevent “re-encryption attacks” like the one you described. Having a randomized encryption algorithm implies that for each message there are very many possible ciphertexts corresponding to it, so when you re-encrypt, even if you are re-encrypting the same message, it’s very unlikely that you’ll get a matching ciphertext.

    • Thank you, David. That’s very helpful indeed.

      What about the leap from polynomials to arbitrary functions? Is it just the case that all functions can be expressed as polynomials, in the rings that are used?

      • fractalcat says:

        The leap from polynomials to arbitrary functions isn’t obvious to me either. From what I can gather, Gentry initially defines an evaluation function which operates on circuits consisting of add and multiply gates, then uses those two operations to define nand; from nand, you can build any circuit of a given depth; and as the evaluate function can execute circuits of arbitrary depth, a series of circuits can be constructed to compute any function that’s computable by a Turing machine.

        This may be completely wrong (no higher education and very limited knowledge of computation theory) – I look forward to a better explanation.

      • davidcash says:

        No problem!

        I am not sure about the best way to go from polynomials to arbitrary functions. My understanding is that are two ways. The first is, as you suggest, to express the function you want to compute as a polynomial. You can always do this, but it’s not very efficient for arbitrary functions, and you will have to fix the degree of the polynomial ahead of time (when you generate the key). The second way is to use the “bootstrapping” technique introduced in the original paper, or one of its recent variants. It’s more complicated, but briefly, it involves expressing the program as a boolean NAND circuit. One homomorphically evaluates this circuit using a clever trick where one repeatedly evaluates a polynomial that corresponds to the decryption circuit with an additional NAND gate. Thus you only have to deal with that one polynomial instead of an arbitrary one.

  2. Paul Roberts says:

    You need to read up a little about group theory. My (limited) understanding is that if you can provide a bijective mapping between all the elements of one group (say polynomials) with the elements on another group (say integers modulo n), then you can prove that mathematical results that apply in one group apply in either…

  3. Pingback: Challenging the Power of Twitter « Bosker Blog

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s