IBM Claims Breakthrough In Analysis of Encrypted Data 199
An anonymous reader writes "An IBM researcher has solved a thorny mathematical problem that has confounded scientists since the invention of public-key encryption several decades ago. The breakthrough, called 'privacy homomorphism,' or 'fully homomorphic encryption,' makes possible the deep and unlimited analysis of encrypted information — data that has been intentionally scrambled — without sacrificing confidentiality." Reader ElasticVapor writes that the solution IBM claims "might better enable a cloud computing vendor to perform computations on clients' data at their request, such as analyzing sales patterns, without exposing the original data. Other potential applications include enabling filters to identify spam, even in encrypted email, or protecting information contained in electronic medical records."
Yeah (Score:3, Insightful)
Right, because we've already figured out everything about cloud computing and it's a totally stable environment ready to be deployed in every company around the globe. Time to take it to the next step.
No More Privacy (Score:5, Insightful)
"perform computations on clients' data at their request, such as analyzing sales patterns"
Or without their request.
If they can analyze the data... (Score:2, Insightful)
then that form of encryption is useless for highly sensitive information.
It's as simple as that.
Re:No More Privacy (Score:3, Insightful)
Or without their request.
The NSA figured that out a long time ago.
But what if it took... a TRILLION times longer? (Score:3, Insightful)
Yeah, you can perform calculations on encrypted data without unencrypting it. But it's just a LITTLE slow. The first step is just showing it can be done, but it's a very long way from useful.
Re:Wikipedia to the rescue (Score:5, Insightful)
Holes are always found - no method is 100% foolproof. The question is will the holes be usable? If the level of effort to exploit the holes is high enough, we may not see them exploited for some time. But the holes are there, and they will be found.
Re:Look but don't see. (Score:2, Insightful)
You've thoroughly misunderstood what this is about, I think. AFAIK this is about performing computations on encrypted data without having to decrypt the data.
Say I have a function F that I want to run on data A to produce data B. i.e. B=F(A)
F is an expensive function to run (big computation), so I'd like to hire the performance of computation service from someone, let's call them MBI, with a huge ass-computer.
But I don't want MBI to know the data A.
So I encrypt it, and give them CryptA instead.
But applying F to CryptA isn't going to give B, and maybe I don't want MBI to know B either!
But say I could derive a function G from function F, that given CryptA, produced an encrypted output CryptB, that when I decrypted gave B. i.e. CryptB = G(CryptA)
So I could give MBI data CryptA and function G, they could computer CryptB for me for a small (large) fee, no doubt - time on a blue gene machine or other large scary linux box isn't all that cheap to provide, though it's often at taxpayer expense.
And then I could decrypt CryptB to get the B I wanted. Since MBI only ever have CryptA, function G and CryptB, I don't leak input A or output B to them (I'm not sure off the top of my head whether they can derive F from G)
i.e. this is to enable provision of a SAFE (well, until someone makes a quantum computer...) computation service that PROTECTS privacy the way current systems don't
Actually, I thought it was "solved" (for cryptographer values of "solved"), just very computationally expensive and that's why people don't do it, I could have been wrong there, not actually a cryptographer.
Homomorphism (Score:5, Insightful)
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.
Re:BAD summary (Score:4, Insightful)
My problem with this is that you'd have to expose the structure of your data, if not its contents. Using your example, the cyphertext might look like: "QEDD32JFS3234DSF31". You'd have to tell the analyzer that integer A starts at index 3 and integer B starts at index 10. That information alone could help the analyzer crack your encryption.
Re:BAD summary (Score:4, Insightful)
Nope, absolutely not ... assuming the processor at least knows that the encrypted data represents integers, then he could simply do the following, using your values above :-
D32JFS3 / D32JFS3 = XXXXXXX (he has now established the encrypted data for the value 1).
Clever idea but it does not work.
First, it's easy to figure out the encrypted data for the value 1: just encrypt the value 1! This is public key encryption.
Second, there are multiple ways of encrypting the value 1. This is randomized encryption.
So it's easy to learn an encryption of the value 1 (or of any value for that matter), but it won't shed any light on what values are actually encrypted, because even if you guess right (i.e. you try encrypting the value 14 and you are later given an encryption of the value 14), the encryptions won't match because there are too many different ways of encrypting the same value.