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."

Re:Marriage equality

[lgw]

Since the first 5 posts are all "homo" jokes, I'm gonna squat here for my on-topic post (heh ... heh ... he said squat).

The main problem I see with the whole idea of homomorphic encryption is it's necessary limitations. If I can get the plaintext results of the difference (subtraction) of the plaintext of two encrypted strings, I can trivially decrypt both if they're English text. (Obviously if I know one of the strings, but less obviously adding, subtracting, or XORing two strings is a trivial cypher these days, more of a compression algorithm really.)

If I can compare two strings, or sort a set of strings in plaintext order, that leaks a lot. If I can compare substrings, and have a large set of strings to work with, that's probably enough to decrypt all the strings in the set (again assuming English or some natural language text, not arbitrary GUIDs).

In order to preserve encryption, the set of operations you can perform on an encrypted DB table without decrypting has to be kept small. Most of the stuff you'd really want to do, like alerting when the value in a column exceeds a bound, or any sort of aggregation of results, must be disallowed. Sure, you can blindly increment or decrement a value, but you can't test the result in any way.

As much as it would be cool for me to be able to stick data in the cloud, encrypted so the provided can't read it, but still have the provider do data grooming for me - you just can't have both.

The ultimate DRM?

[MobyDisk]

Can homomophic encryption be used to create near-perfect DRM?

Current DRM chain:
Raw video stream -> Compress to MPEG -> Encrypt -> Send to customer's player -> Decrypt -> Decompress MPEG -> Cracker grabs video stream here -> Re-encrypt HDCP -> Send to television -> Television decrypts HDCP

Homomorphic DRM chain:
Raw video stream -> Compress to MPEG -> Encrypt -> Send to customer's player -> Decompress without decrypting -> Send to television -> Television decrypts

But this assumes it is possible to perform an immensely complex transformation on the encrypted data. Is that even theoretically possible? Multiplying encrypted numbers is a long way from performing an MPEG decompression on an encrypted string.

Re:Marriage equality

[Samantha Wright]

...and from there, you can go on to implement just about any mathematical operation, as long as you encrypt all of your operands first and don't mind an ungodly number of steps just to do a simple division. The algorithm implementer has to be more trusted than the hardware provider, though, to get arbitrary operations done.

Re:Sounds impractical

[SLi]

The summary doesn't really explain this that well... the benefits here (if I'm reading this correctly) are that someone with a HUGE block of ciphertext and the encryption key can modify slices in situ without having to decrypt the large block and re-encrypt. They can just swap out the old data for the new, based on the index.

This begins to have significant benefits when applied to hosted computing (called Cloud Computing this decade), where, say, all your email is stored encrypted, as is the email index, and you just want to add/remove something without decrypting the entire blob. It also means that cloud hashing becomes significantly easier, as does filesystem-level encryption (since we no longer need to depend on block ciphers, but can use a homomorphic stream cipher and then chop it up after the fact).

Err, no, you are actually reading it completely wrong.

The point is actually that you can give encrypted data, say, some of your company's vital statistics, to an outsider (for example, a consulting agency); that agency can do a computation on that encrypted data (say, their super-secret algorithm that analyzes your company and tells you how to get rich fast) and get an encrypted result, which it then gives back to you. Only you can then decrypt the result.

You get to keep your data secret, and the company doing the computation gets to keep the function they compute secret; the only thing revealed to you is the function applied to your data, and nothing is revealed to the consulting agency.

The big stumbling block to this point has been that the speed gains achieved by homomorphism have been offset by the overhead in implementing the homomorphic algorithms in the first place -- meaning that it's faster to decrypt, modify, re-encrypt.

Homomorphic encryption most certainly is not about speed gains.

Re:Every DRM scheme is vulnerable

[Kookus]

I dunno, I found a device that pretty easily/cheaply rips the content from the tv screen.
I just point my phone at the tv and hit record.

In the old days I used a vhs recorder.

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:As someone who has to deal with HIPAA Requireme

[cryptizard]

It is not that the algorithms have not been well tested. Actually the "algorithms" do not really need to be tested as we have security proofs that reduce to hardness assumptions. The problem is that the hardness assumptions simply have not been around long enough to be thoroughly vetted. RSA is based on the hardness of the RSA assumption (related to the hardness of factoring) which has had 40 years to be broken. These new homomorphic encryption schemes have been around for at most 4 years, which is NOTHING in the scheme of things.

Re:MOD PARENT DOWN

[lgw]

You obviously haven't even read the wikipedia article on homomorphic encryption, much less any of the relevant papers. Every single thing you said was wrong.

Care to actually add something to the discussion. I listed a few things one couldn't do with homomorphic encryption, but would be needed do do anything useful with the encrypted data. Yes, I know full well you can't do those things (e.g., you can't get the plaintext difference between two encrypted strings), which is precisely what I'm complaining about.

Since there's no way for me to tell is a value if greater than X (since that would leak in ways that homomorphic encryption doesn't), I can't send alerts when encrypted data passes an alarm threshold X, or delete email older than X (assuming that metadata is encrypted).

So, anyone, please give some examples of useful processing that someone without the key could do with the data? What is this actually useful for?

Re:Marriage equality

[cryptizard]

Nah because it is also semantically secure [wikipedia.org]. For every plaintext value, there are lots and lots of different ciphertext values (it is a one-to-many mapping). So many, in fact, that knowing the plaintext value of any particular ciphertext doesn't give you any good information.

You do have the problem that anyone can come up with any valid ciphertext and jam it into your computation wherever they want, but we have some other cool stuff for verifying that only authenticated ciphertexts were used and that the function the guy evaluated was the one he was supposed to do. Lots of very cool stuff :-)