Slashdot

"perform computations on clients' data at their request, such as analyzing sales patterns"

Or without their request.

Just FYI this site is whole sale cut and paste ripping IBM press off.

http://www-03.ibm.com/press/us/en/pressrelease/27840.wss

Cool, but I'm half-convinced that holes will be found. The first time a new encryption scheme is put to the test, it usually fails. Still, hopefully, it'll lead to a truly secure scheme.

OK, it looks like a lot of people are missing the point.

What Gentry figured out was a scheme for carrying out arbitrary computations on encrypted data, producing an encrypted result. That way, you can do your computation on encrypted data in the "cloud", but only you can view the results.

If E() is your encryption function, x is your data, and f() is the function you'd like to compute, homomorphic encryption gives you a function f'() such that f'(E(x)) = E(f(x)). But at no point does it actually decrypt your data.

This could be huge for secure computing.

This article needs some clarification. In particular, a lot of the worried comments here show a lack of understanding of the word "homomorphic".

Here's a very simplified example of a homomorphism. I define a function
f(x) = 3x
This function is a homomorphism on numbers under addition. Its image "preserves" the addition operation. What I mean more precisely is
f(a) + f(b) = f(a + b)
That's pretty easy to verify for the function I've given.

Homomorphic encryption is interested in an encryption function f() that preserves useful computational operations. If we take my example as a very very simplified encryption then, say I have two numbers, 6, and 15, and I lack the computational power to do addtion, but I can encrypt my data with my key--3. (I'm generalizing my function to be multiplication by a key. And yes, for some reason I have the computational power to do multiplication. Humor me). I can encrypt my data, f(6) = 18 and f(15) = 45, and pass these to you, and ask you do do addtion for me. You'll do the addition, get 63, and pass this result to me, which I can then decrypt, which yields 21.

Now, my encryption here is very simple and very, very weak, but if you're willing to suspend disbelief, you'll note that the information I've allowed you to handle does not reveal either my inputs or my outputs. (In fact, with the particular numbers I've chosen, you might guess that my key is 9 instead of 3, (though relying on lucky choices or constraining myself to choices which have this property make my scheme rather useless))

If you generalize this to strong encryption and more useful computational operations, you begin to see how homomorphic encryption can be useful. One should note that, no, homomorphic encryption will not be a drop-in replacement for other forms of encryption. (Sending encrypted emails with homormorphic encryption would be unwise. An attacker can modify the data (though, if my understanding is correct, only with other data encrypted with the same key)) Homomorphic encryption simply fills a need that the other forms do not serve.

Hopefully you now also see how the article's use of the word "analysis" can be rather misleading. In particular, one of the earlier comments notes that it might be useful in allowing you to determine if different people's encrypted information is identical. By my understanding, homomorphic encryption would not allow this.

In any case, if my explanation is not enough, here [wikipedia.org]'s the wikipedia article.

A lot of respondents seem to have seized on a spurious notion of what this is all about. That isn't surprising since the Slashdot article and the press release and even the abstract are rather obscure. No sign of a preprint, but the same abstract shows up for a number of colloquiums in the last couple of months. The paper is from a proceedings, so it may itself not be especially profound.

The abstract says: "We propose a fully homomorphic encryption scheme -- i.e., a scheme that allows one to evaluate circuits over encrypted data without being able to decrypt. Our solution comes in three steps. First, we provide a general result -- that, to construct an encryption scheme that permits evaluation of arbitrary circuits, it suffices to construct an encryption scheme that can evaluate (slightly augmented versions of) its own decryption circuit; we call a scheme that can evaluate its (augmented) decryption circuit bootstrappable."

The encryption and compression literature tends to use the word "scheme" where others might say algorithm or transform. "Circuits" here is a term of art (maybe arising originally from actual physical circuits, as in the Enigma machine?)

"An encryption scheme that permits evaluation of arbitrary circuits" suggests only that the possessor of the private key can generate these arbitrary queries, not that anybody and their brother can scavenge the encrypted data. It isn't stated whether such a query also requires the plaintext. It would be pretty cool if one feature were to be able to discard the plaintext post-encryption.

The gimmick appears to be that the arbitrary circuit can include the decryption itself (the bootstrap part). Note that this feature is far more cool (assuming it works) than all the nonsense about cloud computing. Somehow the data are *arbitrarily* available to properly encoded queries without ever being exposed - even to the CPU performing the operations. This processor could be on the same machine, on some remote server, in the cloud or across the galaxy. How cool is that?

A few misconceptions continue to circulate here; let me try to shed some light.

First, the encryption system is apparently not practical in its current form. Maybe improvements will occur some day to make it practical, maybe not. It is still a major theoretical breakthrough because fully homomorphic encryption had often been thought to be impossible in the past. It has been a long sought goal in cryptography and it is remarkable to see it finally achieved. So in practice nobody is going to be doing spam filtering, income tax returns, or anonymous google searches any time soon.

Second, several people have gotten tripped up over an apparent weakness: if you can calculate E(X-Y) you can get an encryption of 0; if you can calculate E(X/Y) you can get an encryption of 1; and from these you could get other encryptions and potentially break the system. This idea fails for two reasons: first, it is a public-key system, so you don't need to go through all this rigamarole to get encryptions of 0, 1, or anything. In public key cryptography, anyone can encrypt data under a given key, without knowing any secrets. So it is already possible to get encryptions of known values, even without the special homomorphic properties. Second, in order for public key systems to be secure, they need to have a randomization property. In randomized encryption, there are multiple ciphertext values that encrypt the same plaintext. Basically, the encryption algorithm takes both the plaintext and a random value, and produces the ciphertext. Each different possible random value causes the same plaintext to go to a different ciphertext. The decryption algorithm nevertheless can take any of these different ciphertext values and produce the same plaintext.

This may be confusing because the most well known public key encryption system, RSA is not randomized. At the time it was invented, this aspect was not well understood. Shortly afterwards it became clear how important randomization is. Other encryption systems like ElGamal do use randomization, and RSA was adapted to allow randomization via what is called a "random padding" layer, known by the technical name PKCS-1. This adds the randomness which allows RSA to be used securely.

One other point is that people are getting hung up about what "fully" homomorphic encryption covers. Exactly what operations can you do? I think the best way to think of it is to go down to the binary level. We know that in our computers, at the lowest level everything is 1's and 0's. These get combined with elementary logical operations like AND, OR, NOT, XOR, and so on. Using these primitive operations, all the complexity of modern programs can be built up.

In the case of the homomorphic encryption, it is probably best to think of the values being encrypted in binary form, as encryptions of 1's and 0's. Keep in mind the point above about randomized encryption: all the encryptions of 1 look different, as do all the encryptions of 0. You can't tell whether a given value encrypts a 1 or a 0. Given these encrypted values, you can compute AND, OR, XOR, NOT and so on with these values, and get new encrypted values as the answers. You don't know the value of the outputs, they are encrypted. Only the holder of the private key, who originally encrypted the data, could decrypt the output. But you can continue to work with these output values, do more calculations with them, and so on.

Let me give an example of how you could do an equality comparison. Suppose you have two encrypted values and want to determine if they are the same. Recall that we are working in binary, so you actually have two sequences of encrypted bits; some are encrypted 1's and some are encrypted 0's, but you can't tell which. So the first thing you compute is the XOR of corresponding bits in the two values: XOR the 1st bits of each value; XOR the 2nd bits of each value, and so on. Now if the values are equal, the results are all encryptions of 0's. If the values are different, some of the results will be encryptions of 1's. But aga