IBM Researchers Open Source Homomorphic Crypto Library 130
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."
Marriage equality (Score:5, Funny)
Re: (Score:1)
Re: (Score:1, Interesting)
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 the
Re:Marriage equality (Score:5, Informative)
Re:Marriage equality (Score:5, Interesting)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:3)
I don't understand how you get from encrypted inputs an
Re: (Score:2)
Re:Marriage equality (Score:5, Interesting)
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: (Score:2)
Re: (Score:2)
I don't understand how you get from encrypted inputs and a mathematical operation that occurs without decrypting the inputs to a distributed search.
There's a lot of gotcha's here but let me give you the gist. When you do a search something like this happens (encrypted or not), your query gets hashed into some feature vector of ones and zero. You can imagine the bits of this feature vectors like 20 questions (first bit: is it alive...) etc. The search company then AND this feature vector against every feature vector of the web pages it has scanned. The ones with a good match are returned to you. That's of course a naive version of searching.
If we
Re: (Score:2)
so then i can do a/a to get 1, and so find E(1), then 1+1 to find E(2) and so on until i have full mapping of plaintext numbers to cyphertext numbers.
Re: (Score:2)
Re: (Score:2)
thanks that makes sense. i couldn't really believe that folk smart enough to make homomorphic crypto would not have though of this.
Re: (Score:3)
Re: (Score:2)
Re:Marriage equality (Score:4, Interesting)
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
Re: (Score:2)
What homomorphic encryption allows is for you to obtain the encrypted sum or product of two ciphertexts
Right, but what good is that? The only scenario in which this stuff is going to come up is hosted/cloud data stores, where the tenant has the keys and the host doesn't (or the moral equivalent thereof in purely internal datacenters where one team must keep data secret from the IT department).
So, as the owner of the data, I have the keys and can already do everything I need. Clever encryption could I theory allow the owner of the hardware to offer various bulk data grooming services, where my data could be
Re: (Score:3)
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
Re:Marriage equality (Score:5, Informative)
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: (Score:2)
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.
You're overselling it. The server can still apply its own labeling (and probably will!) and perform traffic analysis over that; you're still providing a decision procedure even if an elaborate one. What he doesn't learn is what your labeling is, but since you could be using an arbitrary labeling in the first place that's not a huge step forward.
More relevantly though, this mechanism allows you to get summary data without the server knowing what those summary values are. That might or might not be important.
Re: (Score:2)
More relevantly though, this mechanism allows you to get summary data without the server knowing what those summary values are. That might or might not be important.
Damn, hit submit and thought of another point immediately! What I'm not sure of is whether you could hide what type of operation is being performed. Would the server be able to know you're calculating a maximum or an average, even if not what it is? My understanding of the details of homomorphic encryption is rather shaky so I can't be sure about that...
Re: (Score:2)
The serve would always learn the circuit you are using, so he would be able to tell which function you are evaluating over your data. There are methods to
MOD PARENT DOWN (Score:3)
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: (Score:2, Interesting)
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
Re:MOD PARENT DOWN (Score:4, Insightful)
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 [wikipedia.org] 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: (Score:2)
C'mon, I know no one reads TFA or even TFS, but let's at least read the posts we respond to!
lgw: what good is homomorphic encryption? You can't do X, which is needed to be useful.
kumanopuusan: RAWR you know nothing, you can't do X with homomorphic encryption.
lgw: Yes, as I said, you can't do X. So, then, what can you do that's useful without X?
chihowa: understanding of what homomorphic encryption is is fundamentally incorrect - you can't do X
lgw: *facepalm*
Re: (Score:3)
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 i
Re:MOD PARENT DOWN (Score:5, Informative)
Re: (Score:2)
Ahh, that makes a little bit of sense. So that means I could write some carefully constructed query that the host could then run on a server open to the host, and use the result of that for some data grooming? I can see some value there
Of course, today I could run that query on a collocated server that the host didn't have permissions for, but I guess that would require more trust, and might not be practical in some cases.
Or, of course, I could just tag the data with whatever unencrypted meta-data I was w
Re:Marriage equality (Score:5, Insightful)
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: (Score:1)
Good news ciphercloud! (Score:3)
Now you can start offering non-jokey encryption!
Sounds impractical (Score:2, Informative)
Re: (Score:2)
Easy - you write the algorithm with unencrypted data. That's the fun part about your computer being deterministic and all...
Re: (Score:2)
That's the fun part about your computer being deterministic and all...
Well... your computer anyway, not mine [wikipedia.org]. :-)
Re: (Score:2)
Re: (Score:1)
If you're just storing ERP data for customers you can manipulate it without knowing what the data is, only people with passwords would have access to what the data actually is.
Re: (Score:1)
How the heck can you know what operations you needed to perform on the data in the first place if you don't actually know what the data was?
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, a
Re: (Score:3)
Re:Sounds impractical (Score:4, Interesting)
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: (Score:2)
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.
1) You have a bunch of encrpyted data. 2) A third party wants the results of a operation on your data. 3) You're too busy to be bothered with it so you say to a middle man "Wave this magic wand over my data and give me the results." 4) You decrpyt those results and send them to the third party. This will open up a completely new business model; the "data broker", a sort of clearing house or processor of encrypted data that the owning company can safely pass off to these middle men without comprimising the d
Re: (Score:2)
A good example of what this means and why anyone cares is the problem of spam filtering on encrypted messages. Suppose a spammer decided to encrypt spam using your public key; how might your mail server perform a spam check (something which is generally considered to be desirable)? The solution with FH
Correction (Score:2)
Re: (Score:3)
Re: (Score:2)
this wouldn't work because the encryption would be deterministic
How is that? Wherever the encryption algorithm samples random numbers, the FHE evaluator would sample a random number and encode it using the encrypted "0" and "1".
The only tricky part to this is that it might not work if the FHE system does not have function privacy, though I am not sure that requirement is truly necessary.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
this could be useful (Score:2)
This would be great for manipulating encrypted data on hosted servers you could upload your encrypted database never decrypt it so you will not have to worry about your data beings stolen. while you may have to pay more as you are using more resources i can see this being useful in many environments where business are hesitant to move to cloud based servers for fear of privacy breaches of customer data.
Re: (Score:2)
The ultimate DRM? (Score:4, Interesting)
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: (Score:2)
Television decrypts
I see a possible flaw in your DRM...
Re:Every DRM scheme is vulnerable (Score:4, Interesting)
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: (Score:2)
It's always possible to get the audio un-DRMed with almost no loss of quality by just hooking a recorder up to the speaker cables and doing some basic electronics fiddling.
Video is much harder though.
Re: (Score:2)
Re: (Score:2)
If you didn't want the ability to FF or Rewind. You can't even just skip ahead by B-Frame if the frame boundaries are unknown without decrypting. This could be solved by sending a piggyback unencrypted stream of frame sizes. But it would just be redundant data.
Re: (Score:2)
Re: (Score:3)
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: (Score:3)
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? (Score:5, Funny)
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.
Re: (Score:1)
You made me spill my drink
Re: (Score:3)
Re: (Score:2)
What you're missing is knowing the key to encrypt 0 and 1. If you already have the key to encrypt/decrypt the data, then you're already set. Without the encryption keys, how do you know whether 0 is represented by '852ee92374f0527bf7499161c' or '6dba27a49b5e0fc6979' (or whatever else)?
Re: (Score:3)
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.
zero (Score:2)
So... multiply by zero. You now know the hidden value is zero
In order to multiply by zero, you would need to already know the encrypted value of zero.
Zero is obtained by homomorhopically subtracting a record form itself.
Re: (Score:1)
E(0) is E(a) - E(a)
E(1) is obtained by E(a)/E(a).
E(-1) is E(0) - E(1)
E(2) = E(1) + E(1) ...
E(n) = E(n-1) + E(1)
E(-n) = E(-(n-1)) + E(-1)
And there you go. All the integers - from one encrypted input.
And you can even recover your cyphertext *if* the homomorphic set has a 'is equal to' or a 'is not equal to' operator.
for (i = 0, ei = E(a)-E(a); ei is_equal E(a); i=i+1, ei = ei plus E(a) div E(a));
At the end of the loop, i == a.
Re: (Score:1)
Of course, this is also why the IBM system only has '+' and '*' as operators.
Which severely limits the operations you can do on the encrypted system (so long as you aren't given E(-1) as an input).
If given E(-1) as input, you can recover all the integers again, and you can do any arithmetic set of operations.
I think testing for equality is strictly verboten under their system.
Re: (Score:2)
brainfuck?
Re: (Score:2)
As someone who has to deal with HIPAA Requirements (Score:4, Informative)
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: (Score:2)
Re: (Score:2)
How do you even judge that something is "encrypted" if you are using a scheme that some grad student made up like a month ago?
This is a problem that has already been solved. The answer is: You treat it like it's simply "security by obscurity" and assume it will be broken any day soon. The sad fact is that this is true for most of the encryption schemes thought up over the years.
And honestly, if homomorphic encryption can't work with a well tested and analyzed encryption algorithm, I'm not sure I'm very impressed about it..
Re:As someone who has to deal with HIPAA Requireme (Score:4, Interesting)
Re: (Score:2)
Can I ask you what are the algorithms behind this secure voting method [youtube.com]? When I watched this presentation I thought he was talking about homomorphic encryption, but after I read about it I realized it couldn't be, since the computation required for processing millions of ballots would be far too much.
Re: (Score:2)
There is a famous voting system by Rivest which does use homomorphic encryption though, and I can explain to you why it still remains efficient. This article is specifically about fully homomorphic encryption schemes, w
Re: (Score:2)
http://blogs.msdn.com/b/windowsazure/archive/2012/07/25/security-privacy-amp-compliance-update-microsoft-offers-customers-and-partners-a-hipaa-business-associate-agreement-baa-for-windows-azure.aspx [msdn.com]
http://arstechnica.com/business/2011/09/amazon-cloud-earns-fisma-government-security-accreditation/ [arstechnica.com]
Re: (Score:1)
None of the big players except Amazon's EC2 and Microsoft's Azure:
http://blogs.msdn.com/b/windowsazure/archive/2012/07/25/security-privacy-amp-compliance-update-microsoft-offers-customers-and-partners-a-hipaa-business-associate-agreement-baa-for-windows-azure.aspx [msdn.com]
http://arstechnica.com/business/2011/09/amazon-cloud-earns-fisma-government-security-accreditation/ [arstechnica.com]
Thank you. I was aware that they were in technical compliance, but I was not aware that Azure had started offering the business associate agreement. The link below seems to indicate that AWS is still "looking into" the matter, but I haven't found anything conclusive that says they will offer it. Needless to say, I'm starting a project immediately to begin an Azure deployment for my organization.
https://forums.aws.amazon.com/thread.jspa?messageID=444933 [amazon.com]
Scary stuff (Score:2)
Homomorphic encryption is scary stuff, one could use it to make malware or drm schemes that would be, for all practical intents and purposes, impossible to reverse engineer:
http://www.kuro5hin.org/story/2010/12/15/151617/78/ [kuro5hin.org]
Re: (Score:2)
Examples? (Score:1)
The documentation is mostly reference material and very dense. Anybody have some examples on how to actually use the library?
Re: (Score:2)
Numerical Porn (Score:3)
Screw encryption, I want hashing! (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Sure there are classes harder than NP, but it is necessary that our problems be in NP because otherwise it would be intractable for legitimate users. Take public key cryptography
Re: (Score:3)