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

[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:Marriage equality

[DuckDodgers]

Steve Gibson did a podcast in which he tried to put homomorphic encryption in layman's terms ( here, about 25 minutes in is the meat of the discussion: http://twit.tv/show/security-now/376 ). What he said was possible, but didn't explain even in general terms, would be a distributed encrypted search engine in which you could send search request into it and get results, and the company hosting the service would not even know what you searched for.

I don't understand how you get from encrypted inputs and a mathematical operation that occurs without decrypting the inputs to a distributed search.

Re:Marriage equality

[cryptizard]

It can be made public key. It is also semantically secure, so knowing the plaintext value of any one ciphertext gives you no information about the value of other ciphertexts.

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:Marriage equality

[goombah99]

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.

Well no.
here's just one possible way to deal with that. For each string you form two different strings by XOR the string with a random string and the complement of that random string. Now You encrypt each String in the pair with a different key in a homomorphic way.

A third party can now do whatever albelian operations they want on either of these strings but they have no way to combine the two results since the keys are different.

However you are able to do this by doing the operations on both strings then at the very end decrypting them and Xoring the result.

Voila.

Works for voting systems where one person gets to have the keys, and one person gets to maintain the database of encrypted votes. As long as they don't collude, then the data base holder can sum all the ballots up but not know what any ballot is. The key holder can determine the sum but never get access to the individual ballots.

Re:Marriage equality

[Rich0]

Well, I imagine they might be useful for solving some esoteric encryption problems. Imagine I have a document that is digitally signed by somebody you trust, but I don't want to share the whole thing with you. I want to redact the document, and then have the non-redacted parts still be signed. Maybe functions like these might let me derive a new signature for the redacted content in a way that tells the recipient that the unredacted part is valid, but that it wasn't the original either.

I don't know that anybody has come up with a way to solve that particular problem - I just use it as an example of the sort of case where being able to manipulate encrypted data without a key could be useful. There are lots of cases where you want groups of people to be able to work with data where no individual has all the keys, but some group of individuals can still read it, and this falls into the same sort of category of interesting techniques that might solve very particular problems.

Re:Marriage equality

[cryptizard]

So, let me first say that the main selling point for this technology is that it allows you to outsource your computation. You can use a low powered device like a cell phone and take advantage of more powerful computation in the cloud, while maintaining data privacy. You are correct that certain things will be leaked, like if I am storing encrypted email and I search for all emails sent by so-and-so then the server would learn how many emails I have from that guy. This is still a huge advantage over what we have now.

Now, I can outline a cool use that you probably have not thought of which is a little different. Imagine that a server is storing some really sensitive stuff for me. Obviously I don't trust the server so I am encrypting all my files. If he is really sneaky, however, he can learn something about the contents of those files by watching when, where and how often I access them. We call this the access pattern, and usually people just write this off as a cost of doing business. However, with homomorphic encryption we can hide even that!

Since I can evaluate any program homomorphically over my data, I write a program that says "return file number x" and give it an encrypted value, say 50, for x. The server now evaluates this program, with my encrypted 50, over the entire set of files. What he gives back to me is my file that I wanted, but from his point of view he can't actually tell which file he gave me! All he knows is he ran a circuit over all the files in the database, with my input that specifies which one I want, but he can't tell what my input is because it is encrypted.

Re:Marriage equality

[cryptizard]

Nah because it is also semantically secure. 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 :-)

Good news ciphercloud!

[GameboyRMH]

Now you can start offering non-jokey encryption!

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:The ultimate DRM?

[pipatron]

You can generally not compress an encrypted stream of data.

Good encryption masks all the structure/redundancy from the data, which the compressor needs in order to remove useless bits.

Re:The ultimate DRM?

[steelfood]

No. And it illustrates just how useless DRM and activities around developing DRM actually are. There's always one place where the information has to come out decrypted. That place typically sits right in front of your sensory organs.

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.

As someone who has to deal with HIPAA Requirements

[jforr]

This will be revolutionary for the healthcare industry.

Let me explain for those of you who have never dealt with HIPAA. HIPAA requires that an entity possessing protected healthcare information(PHI) keep that data safe and secure. Additionally, any outside entity coming in contact with PHI must sign a business associates agreement also agreeing to keep any PHI in their possession safe. None of the major cloud players will sign such agreements, which means any PHI can't go into the cloud. This means any practical deployment of say a hadoop cluster to reduce the process time of a large ETL job isn't feasible.

Now there is a tiny loophole in that encrypted PHI isn't treated as PHI at all. This means we can pass data through cloud services to backup for example, but doing any manipulating of the data is impossible due to the fact that as soon as you decrypt it, it's PHI and that's a big no-no. And this is where we lead back to homomorphic cryptography being revolutionary for the world of healthcare data.

Re:Sounds impractical

[cryptizard]

All it means for an encryption to be fully-homorphic is that 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). The benefit of this is that you can arithmetize any program into a circuit containing only addition and multiplication gates, meaning you can run any program you want over the encrypted data. I'm not sure what you mean by your second paragraph. Blocks are already very very small in existing ciphers so you are never required to download a whole thing and reencrypt it (if you are using an appropriate mode of operation, CBC obviously would not work for this).

Re:Wait... what?

[cryptizard]

It is a probabilistic encryption. That is, there are many different encryptions of the same value, to the point that knowing the plaintext that corresponds to a particular ciphertext does not give you any information. All modern encryption schemes are like this in order to prevent the attack you describe (or a similar one).

Re:Wait... what?

[betterunixthanunix]

https://en.wikipedia.org/wiki/Semantic_security

Let's put it this way: you could do the same with any public key cryptosystem by using the public key to encrypt the dictionary you described. The reason that does not work is that there are many (exponentially many in the security parameter) possible encryptions of each plaintext.

Re:Correction

[cryptizard]

Nah, this wouldn't work because the encryption would be deterministic. If I wanted to test whether you had encrypted a certain bitstring I could recreate the process you used and compare the results. The actual way they do it in the Gentry paper is to publish an encryption of 1 and a whole bunch of encryptions of 0. Then your encryption process is to pick a random subset of those zeroes, add them together to get a new encryption of zero and then add the one if you are encrypting a 1. If the sparse subset sum assumption is true, then it will be hard to determine whether this ciphertext is the result of summing a bunch of zeroes and a one or just a bunch of zeroes.

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.

Numerical Porn

[nanospook]

With the erection of homomorphic data centers, we should be able to pound our data injections directly and deeply into encrypted data mounds using a direct boaring method without worrying about compromising data health.

MOD PARENT DOWN

[kumanopuusan]

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.

Re:MOD PARENT DOWN

[chihowa]

Your understanding of what homomorphic encryption is is fundamentally incorrect. If you apply an operator to an encrypted value in a homomorphic system, the result is also encrypted. So, since the initial values and the results are both encrypted, no information is leaked.

Your entire missive above was predicated on the fact that the results of the function would be plaintext, so as the GP so eloquently put it, "Every single thing you said was wrong." Seriously, the first sentence of the wikipedia page makes it fairly clear:

Homomorphic encryption is a form of encryption which allows specific types of computations to be carried out on ciphertext and obtain an encrypted result which decrypted matches the result of operations performed on the plaintext.

Re:MOD PARENT DOWN

[cryptizard]

Nobody said these things weren't possible, just that homomorphic encryption out of the box does not do them. There are recent techniques for functional encryption, which use FHE as a component, that allow these exact scenarios. As you pointed out though, you have to be very careful if you don't want to ruin security. The way they work now, you can supply a server with a specific token which allows him to evaluate one very specific function on your encrypted data and get the plaintext result of that function. For instance, you could give your email server a token which allows him to run spam filtering over your incoming emails and output a plaintext bit which is '1' if it is spam and '0' if it is not. The security property of these schemes is that you cannot learn any information other than the output of this function run over encrypted data. It is veeery tricky at this point because you could leak some dangerous information unknowingly, but the techniques do exist.

Re:MOD PARENT DOWN

[cryptizard]

If you search and the search returns results, you are probably leaking because an observer can keep track of what sectors of the disk the results came from, and what bits passed through the registers of the CPU as it executed compare instructions, and use that to gain information about the data using statistical analysis.

A homomorphic search would not operate the way you are thinking. It would have to compute over the entire set of possible results (otherwise, as you say, the adversary learns at least that some results are not possible) and piece by piece obliviously combine them. As a simplification, if you know your search is going to only return one result then you can have the server run a circuit over each file which evaluates whether that file will be the result or not. If it is, out comes an encrypted one, if it is not then it will be an encrypted zero. The server then multiplies the file itself by this encrypted result and adds it to a running total. All the files which weren't chosen will be zeroed out and the single file you want will end up in this "register", although the server has no idea which one you wanted and which ones were zeroed out.

Re:Really?

[cryptizard]

You're missing the point, this is not being released so that people can actually use it. Keys in this system measure in the gigabytes, and single multiplications take seconds. It is so researchers can apply their new ideas on how to make it more efficient without having to code this whole thing from scratch. It is a great help for research.

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.