IBM Claims Breakthrough In Analysis of Encrypted Data

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

Comments

First post!

[fenring]

Have you seen the new neighbours. I think they're homomorphic.

No More Privacy

[basementman]

"perform computations on clients' data at their request, such as analyzing sales patterns"

Or without their request.

Re:No More Privacy

[John Hasler]

Everything remains encrypted throughout the process, including the output. Only the client can read the results. That is the point.

Fully homomorphic encryption using ideal lattices

[grshutt]

The abstract for Gentry's article can be found at: http://doi.acm.org/10.1145/1536414.1536440

Since it's close to being slashdotted...

[Magic5Ball]

IBM researcher solves longstanding cryptographic challenge
Posted on 25 June 2009.
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.

IBM's solution, formulated by IBM Researcher Craig Gentry, uses a mathematical object called an "ideal lattice," and allows people to fully interact with encrypted data in ways previously thought impossible. With the breakthrough, computer vendors storing the confidential, electronic data of others will be able to fully analyze data on their clients' behalf without expensive interaction with the client, and without seeing any of the private data. With Gentry's technique, the analysis of encrypted information can yield the same detailed results as if the original data was fully visible to all.

Using the solution could help strengthen the business model of "cloud computing," where a computer vendor is entrusted to host the confidential data of others in a ubiquitous Internet presence. It 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. The breakthrough might also one day enable computer users to retrieve information from a search engine with more confidentiality.

"At IBM, as we aim to help businesses and governments operate in more intelligent ways, we are also pursuing the future of privacy and security," said Charles Lickel, vice president of Software Research at IBM. "Fully homomorphic encryption is a bit like enabling a layperson to perform flawless neurosurgery while blindfolded, and without later remembering the episode. We believe this breakthrough will enable businesses to make more informed decisions, based on more studied analysis, without compromising privacy. We also think that the lattice approach holds potential for helping to solve additional cryptography challenges in the future."

Two fathers of modern encryption - Ron Rivest and Leonard Adleman - together with Michael Dertouzos, introduced and struggled with the notion of fully homomorphic encryption approximately 30 years ago. Although advances through the years offered partial solutions to this problem, a full solution that achieves all the desired properties of homomorphic encryption did not exist until now.

IBM enjoys a tradition of making major cryptography breakthroughs, such as the design of the Data Encryption Standard (DES); Hash Message Authentication Code (HMAC); the first lattice-based encryption with a rigorous proof-of-security; and numerous other solutions that have helped advance Internet security.

Craig Gentry conducted research on privacy homomorphism while he was a summer student at IBM Research and while working on his PhD at Stanford University.

from the horses mouth

[Anonymous Coward]

Just FYI this site is whole sale cut and paste ripping IBM press off.

http://www-03.ibm.com/press/us/en/pressrelease/27840.wss

Re:Wait, what?

[moogied]

Yes, yes you are.

The point is not to read the content, but to enable a computer to analyze the content in such a way that they can deduce statistics and patterns from it. FTFA:

computer vendors storing the confidential, electronic data of others will be able to fully analyze data on their clients' behalf without expensive interaction with the client, and without seeing any of the private data

I don't need to know that you love apples to know you definitely love the same thing as 14 other people. Lets assume that we have 20 encrypted sets of data. Lets also assume the 20 sets say basically the same thing but because of the encyrption method look nothing a like from the raw data perspective. If you go ahead and find a way to analyze the encryption enough to know that the 20 emails all contain a similar message, but not enough to actually know what the message is... well then! You could go ahead and store all of ebay's customer information and do massive amounts of data crunching for them, without ever actually seeing any data.

This is a huge problem in IT, where admins need access to the databases in order to see how the data is being stored, how the tables are working, etc etc.. but can't actually have access to the database because then they might see customer information. So you either let joe-bob admin in there and let him see all the data, or you don't. Now you can let the admin in there, they can determine anything they might want to know, but they never actually see any exact data.

No, I don't know anything about the math portion.. but thats basically what they are trying to say in the article. I think. :)

Wikipedia to the rescue

[Dr. Manhattan]

With fully homomorphic encryption, you can perform operations on the encrypted data, in encrypted form, that produces encrypted output. Sort of like doing a database query on encrypted data, that produces an encrypted result. So you could store your data somewhere in encrypted form, ask the host to perform some operations using their CPU cycles, and send you the result. You decrypt the result yourself, the host never sees unencrypted data at any point.

Cool, but I'm half-convinced that holes will be found. The first time a new encryption scheme is put to the test, it usually fails. Still, hopefully, it'll lead to a truly secure scheme.

BAD summary

[spun]

You can not analyze the data. You can perform calculations on it without knowing what it is. So, for instance, you could encrypt all your tax info, send it to a company that processes the encrypted data without decrypting it, and sends you back your encrypted tax return, without ever having seen any of your financial detail.

simple explanation

[Anonymous Coward]

OK, it looks like a lot of people are missing the point.

What Gentry figured out was a scheme for carrying out arbitrary computations on encrypted data, producing an encrypted result. That way, you can do your computation on encrypted data in the "cloud", but only you can view the results.

If E() is your encryption function, x is your data, and f() is the function you'd like to compute, homomorphic encryption gives you a function f'() such that f'(E(x)) = E(f(x)). But at no point does it actually decrypt your data.

This could be huge for secure computing.

Homomorphism

[NAR8789]

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's the wikipedia article.