3 ms·

Here is a question that’s puzzling me. Since this thread has already dropped off the front page, and it probably won’t be seen by many people, I’ve also posted

Here is a question that’s puzzling me. Since this thread has already dropped off the front page, and it probably won’t be seen by many people, I’ve also posted it at http://bosker.wordpress.com/2011/07/31/something-i-don’t-understand-about-homomorphic-encryption/ http://bosker.wordpress.com/2011/07/31/something-i-don’t-und... The homomorphic encryption techniques 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 <em>actually</em> 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? Anyone?

nhaehnle 15y ago
You are assuming that encrypting is a bijection, i.e. that for every plaintext, there is only one possible ciphertext. One of the first things you learn in a public key cryptography is that you have to add random bits in the computation of the ciphertext, either via simple random padding (in the case of RSA) or via some more involved steps (in the case of cyclic group-based cryptography). I don't know much about homomorphic encryption (the concept has always seemed contrived to me - if you don't trust your cloud provider, hosting your own servers will always be much more efficient), but I assume they use similar tricks. As for the thing about polynomials: it should be obvious that any polynomial-time computation on an input of a fixed size can be expressed by a DAG of logic gates. Logic gates can in turn be represented by simple polynomials over the field F_2 = { 0, 1 }, and the composition of gates is then simply the composition of polynomials. Since we're talking about fixed-size inputs, this does not really capture the full Turing machine model. However, since all practical encryption schemes can be broken via brute force in exponential time anyway, it only really makes sense to worry about implementing polynomial-time computations in the context of homomorphic encryption.

nhaehnle 15y ago

You are assuming that encrypting is a bijection, i.e. that for every plaintext, there is only one possible ciphertext. One of the first things you learn in a public key cryptography is that you have to add random bits in the computation of the ciphertext, either via simple random padding (in the case of RSA) or via some more involved steps (in the case of cyclic group-based cryptography). I don't know much about homomorphic encryption (the concept has always seemed contrived to me - if you don't trust your cloud provider, hosting your own servers will always be much more efficient), but I assume they use similar tricks. As for the thing about polynomials: it should be obvious that any polynomial-time computation on an input of a fixed size can be expressed by a DAG of logic gates. Logic gates can in turn be represented by simple polynomials over the field F_2 = { 0, 1 }, and the composition of gates is then simply the composition of polynomials. Since we're talking about fixed-size inputs, this does not really capture the full Turing machine model. However, since all practical encryption schemes can be broken via brute force in exponential time anyway, it only really makes sense to worry about implementing polynomial-time computations in the context of homomorphic encryption.