IBM Solves Cryptographic Cloud Security Challenge
Reuven Cohen
---
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.
--
Reuven
CCIF Instigator
Sam Johnston
I usually don't post press releases, but this one sounded almost too good to be true.
As I said before:
The Cloud equivalent of an electron could be a standardised workload consisting of a small bundle of (encrypted) data and the code required to perform an action upon it.
Anyway kudos to IBM for looking at this - anything which gets us closer to this goal (or indeed even raises awareness of it) is a good thing.
Security includes confidentiality, availability and integrity - currently we rely on our providers for all three but with crypto we don't need to worry about confidentiality and we can at least verify integrity. With Intercloud standards we'll be able to nail availability and integrity too.
Sam
Michael Maximilien
Reuven Cohen
Gentry's elegant solution has a catch: It requires immense computational effort. In the case of a Google search, for instance, performing the process with encrypted keywords would multiply the necessary computing time by around 1 trillion, Gentry estimates. But now that Gentry has broken the theoretical barrier to fully homomorphic encryption, the steps to make it practical won't be far behind, predicts professor Rivest. "There's a lot of engineering work to be done," he says. "But until now we've thought this might not be possible. Now we know it is."
ruv
Gary Mazz
I really dislike these types of press releases, especially on this list.
First, it insults our intelligence with that comment about neurosurgery;
second edge vulnerabilities need to be solved first...
A hacker muslix64 took less than 24hours to crack BlueRay because he
couldn't see his movie... I wonder how long it will take to crack this
lattice scheme if there is something really important someone wants...
The algebraic solve in the paper should be an interesting read.
-gary
Paulo Calcada
Paulo
Gary Mazz
different prime number, keys or schemes together with a map (the
homomorphism), basically a list. The ideal lattice is a
multi-dimensional prime number structure. From those two items, I'm
suspect, putting plainly, they have a list of keys that may be shared in
certain vectors. It's not an easy thing to do by any means.
The big problem with all this encryption stuff is pass phase management
and key setup between parties; which usually includes third party
information a validation digest or something like that. Having an
infinite prime number source to create a key that cannot be "cracked" is
important to both cyphering and the validation digests, but a
computationally intensive to do.
Sometimes its easier to figure out a pass phase than cracking the keys.
I can't tell you how many times I've seen passwords written on a sticky
note stuck to a monitor. :)
-gary
Paulo Calcada wrote:
> Gary, I totally agree with you, we are talking on a new encryption
> schema, not a layer that we will add on top of what we well know nowadays.
>
> Paulo
>
>
> 2009/6/25 Gary Mazz <garymaz...@gmail.com
Greg Pfister
discussion. Wondered whether I should wait to do it here, guess I
should. Anyway:
********
Reuven, take a look at the Wikipedia entry on homomorphic encryption
to find out what the press release has overblown. The relevant part
for me:
"His [Gentry's] scheme can potentially support an unbounded number of
additions and multiplications, except that a bound on the number of
multiplications must be specified in advance at the time of key
generation (and the public-key size grows linearly with the number of
multiplications allowed). Security of this scheme has not yet been
proven to hold based on widely accepted assumptions."
So, assuming this is an accurate statement of what's in the locked-
down in ACM paper (which I probably couldn't understand anyway), we
can conclude the following:
- you can't do *any* computation without decrypting, just addition and
multiplication, and you have to know the # of multiplies ahead of
time. For example, I doubt you can follow a pointer or perform a
comparison (XOR and AND).
- you can't do the adds/muls on something encrypted using, say, 128-
bit AES. You have to use his new encryption algorithm. His may be just
fine, but we don't know that yet.
This work is apparently a major step forward. It clearly doesn't solve
the whole problem of data security in clouds.
*******
Greg Pfister
http://perilsofparallel.blogspot.com/
Reuven Cohen
Also the fact it requires the necessary computing time by around 1 trillion is pretty funny stuff.
(P.S. We need to figure out how to sync the linkedin & google groups)
ruv
Gary Mazz
I'm still looking for the paper. There two separate areas where ideal
latice technology may be used; in the encryption process, or the key
generation process or both. Since the press release references prime
number latices and implies multiple levels of trust, I'm suspect the
works are in the area of key generation. possibly a new key scheme for
constructing layered keys.
-gary
Gary Mazz
Here is Craig Gentry's Presentation
You may want to brush up on your algebra and set theory.
Here is the pdf:
http://av.fields.utoronto.ca/slides/08-09/crypto/gentry/download.pdf
Here is the with voice (realmedia):
http://www.fields.utoronto.ca/audio/08-09/crypto/gentry/index.html?2;large#slideloc
Here is the amc page to download the paper:
http://portal.acm.org/citation.cfm?id=1536414.1536440
AMC cost about $200 to join.
Here is an earlier paper on multiparty systems based on hamming distances:
http://www.cs.rutgers.edu/~rebecca.wright/Publications/talg06.pdf
Note: There are 58 references in Craig Gentry's paper, the earliest
dated is 1978
R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital
signatures and public-key cryptosystems. In Comm. of the ACM, 21:2,pages
120--126,1978
-gary
Sam Johnston
July 9, 2009
Homomorphic Encryption Breakthrough
Last month, IBM made some pretty brash claims about homomorphic encryption and the future of security. I hate to be the one to throw cold water on the whole thing -- as cool as the new discovery is -- but it's important to separate the theoretical from the practical.
Homomorphic cryptosystems are ones where mathematical operations on the ciphertext have regular effects on the plaintext. A normal symmetric cipher -- DES, AES, or whatever -- is not homomorphic. Assume you have a plaintext P, and you encrypt it with AES to get a corresponding ciphertext C. If you multiply that ciphertext by 2, and then decrypt 2C, you get random gibberish instead of P. If you got something else, like 2P, that would imply some pretty strong nonrandomness properties of AES and no one would trust its security.
The RSA algorithm is different. Encrypt P to get C, multiply C by 2, and then decrypt 2C -- and you get 2P. That's a homomorphism: perform some mathematical operation to the ciphertext, and that operation is reflected in the plaintext. The RSA algorithm is homomorphic with respect to multiplication, something that has to be taken into account when evaluating the security of a security system that uses RSA.
This isn't anything new. RSA's homomorphism was known in the 1970s, and other algorithms that are homomorphic with respect to addition have been known since the 1980s. But what has eluded cryptographers is a fully homomorphic cryptosystem: one that is homomorphic under both addition and multiplication and yet still secure. And that's what IBM researcher Craig Gentry has discovered.
This is a bigger deal than might appear at first glance. Any computation can be expressed as a Boolean circuit: a series of additions and multiplications. Your computer consists of a zillion Boolean circuits, and you can run programs to do anything on your computer. This algorithm means you can perform arbitrary computations on homomorphically encrypted data. More concretely: if you encrypt data in a fully homomorphic cryptosystem, you can ship that encrypted data to an untrusted person and that person can perform arbitrary computations on that data without being able to decrypt the data itself. Imagine what that would mean for cloud computing, or any outsourcing infrastructure: you no longer have to trust the outsourcer with the data.
Unfortunately -- you knew that was coming, right? -- Gentry’s scheme is completely impractical. It uses something called an ideal lattice as the basis for the encryption scheme, and both the size of the ciphertext and the complexity of the encryption and decryption operations grow enormously with the number of operations you need to perform on the ciphertext -- and that number needs to be fixed in advance. And converting a computer program, even a simple one, into a Boolean circuit requires an enormous number of operations. These aren't impracticalities that can be solved with some clever optimization techniques and a few turns of Moore's Law; this is an inherent limitation in the algorithm. In one article, Gentry estimates that performing a Google search with encrypted keywords -- a perfectly reasonable simple application of this algorithm -- would increase the amount of computing time by about a trillion. Moore’s law calculates that it would be 40 years before that homomorphic search would be as efficient as a search today, and I think he’s being optimistic with even this most simple of examples.
Despite this, IBM’s PR machine has been in overdrive about the discovery. Its press release makes it sound like this new homomorphic scheme is going to rewrite the business of computing: not just cloud computing, but "enabling filters to identify spam, even in encrypted email, or protection information contained in electronic medical records." Maybe someday, but not in my lifetime.
This is not to take anything away anything from Gentry or his discovery. Visions of a fully homomorphic cryptosystem have been dancing in cryptographers' heads for thirty years. I never expected to see one. It will be years before a sufficient number of cryptographers examine the algorithm that we can have any confidence that the scheme is secure, but -- practicality be damned -- this is an amazing piece of work.