IBM Researchers Open Source Homomorphic Crypto Library

mikejuk writes with news of an advancement for homomorphic encryption and open source: "To be fully homomorphic the code has to be such that a third party can add and multiply numbers that it contains without needing to decrypt it. In other words they can change the data by working with just the encrypted version. This may sound like magic but a fully homomorphic scheme was invented in 2009 by Craig Gentry. This was a step in the right direction but the problem was that it is very inefficient and computationally intensive. Since then there have been a number of improvements that make the scheme practical in the right situations Now Victor Shoup and Shai Halevi of the IBM T J Watson Research Center have released an open source (GPL) C++ library, HElib, as a Github project. The code is said to incorporate many optimizations to make the encryption run faster. Homomorphic encryption has the potential to revolutionize security by allowing operations on data without the need to decrypt it."

Comments

Marriage equality

[Anonymous Coward]

All cryptos should be able to marry any other crypto. Anyone that is homomorphic should really broaden their horizons.

Re:Marriage equality

[cryptizard]

I think you are misunderstanding. What homomorphic encryption allows is for you to obtain the encrypted sum or product of two ciphertexts. That is, there exists some efficient operation o such that E(a) o E(b) = E(a+b) and another operation u such that E(a) u E(b) = E(a*b). What you are describing is closer to functional encryption, in which case the function which you are allowed to evaluate over the ciphertexts is severely limited and must be explicitly granted by the owner of private key.

Re:Marriage equality

[cryptizard]

Sure, that's pretty easy. We can even do it without homomorphic encryption (do a google scholar search for encrypted keyword search, there is lots of stuff with varying levels of security and utility). A quick explanation, which might convince you, is that you can actually run any program you can think of using fully homomorphic encryption.

First, suppose that any program can be written down as a circuit (it can). Now, we know from boolean theory that AND gates and XOR gates are functionally complete, that is any circuit you can write with other gates, you can rewrite with only AND and XOR gates. You might know it with AND and NOT gates, but it is easy to show that XOR can actually implement NOT so that also works. Now, with two bits, AND is really just multiplying the bits (1 AND 1 = 1, any other combo has at least one zero and is 0). XOR, on the other hand is just adding the bits, with the weird case that 1 + 1 = 0, which actually is bitwise addition ignoring the carry (mod 2). So, now we can implement any program as a circuit, any circuit with only AND and XOR gates, and we can do those AND and XOR gates with addition and multiplication. Therefore, we can do anything we want over homomorphically encrypted ciphertexts, with a suitable compiler that will translate our program into those operations!

Now that is a very general construction, so it might not be particularly interesting to your problem, but what it does show is that we can really do anything over the encrypted inputs that we could do with unencrypted inputs. Since Google can run their search algorithm over your unencrypted query, they would also be able to do it over your encrypted query.

Re:The ultimate DRM?

[Rich0]

They're working on neurological DRM. Pretty soon you'll go to the movies and leave talking about how much you enjoyed it, without actually knowing what the story was about or who the actors were, but with a general desire to buy products made by Coca Cola.