New Developments in Cryptography and Privacy
posted by Deven Desai
According to Help Net Security, Craig Gentry, a researcher at IBM, appears to have found a way to allow “the deep and unlimited analysis of encrypted information – data that has been intentionally scrambled – without sacrificing confidentiality.” The solution involves a an “ideal lattice.” I’ll leave the explanation of all the math to the math/computer science folks. As the Help Net article notes, the solution seems to enable some great advantages for anyone providing cloud computing for:
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.
It all sounds wonderful. One could have encrypted data and let others data mine while maintaining anonymity or privacy. Yet, something seemed odd to me. So I did what lawyers do, I called someone who knew more about computer science and asked for some help. That person explained that yes this could mean one could query an encrypted database without decrypting the data. The example to consider is a database of book purchases. One could ask how many people bought both book A and book B and see that result without ever seeing what a specific person purchased. Great, right? Not so fast.
As this person reminded me, with other sources of information one can figure out what a specific person did. That reminded me of the AOL debacle. With a little work, people were able to figure out who the anonymous subjects were.
All of which highlights that privacy is not binary. The cluster of information and the ability to analyze it seems often, if not always, to lead to problems about the use of information. So if this breakthrough allows a company or the government to claim that we should remain calm and all is well, we may want to remain clam but show how all may not be well. A few regulations about the use of the data even if supposedly anonymous, might allow the beneficial aspects of the solution to thrive while limiting the harms that can occur.
Image: WikiCommons
By: Gwenda; License: Public Domain
(My apologies to CS folks if the image does not match the breakthrough’s area of encryption)
June 30, 2009 at 11:35 am
Tags: cloud computing, cryptography, Privacy
Posted in: Cyberlaw, Google & Search Engines, Privacy, Privacy (Consumer Privacy), Privacy (Electronic Surveillance), Privacy (Law Enforcement), Technology
Print This Post
Responses (7)
Steven M. Bellovin - June 30, 2009 at 12:16 pm
Your overall point is very correct — privacy at one layer does not mean protection at another layer.
It’s also way too soon to start worrying about the practical applications. To quote (with permission) some email sent by a colleague of mine:
(And no, the diagram bears no relation to this work; it shows a so-called “mode of operation” of a standard cipher like the Advanced Encryption Standard, and is about 30 years old…)
Deven - June 30, 2009 at 2:29 pm
Steven
Thanks. First I agree, quite an accomplishment. Second, I am not sure that one has to wait to think about the possible problems. We often wait too long and react rather than come up with a better balance. NOW I think you are saying that there should not be a regulation that would stop this type of research and progress in the field. If so, amen. That type of reaction would be foolish.
Last, thanks for the clarification as to what the image is about. I was not trying to show the breakthrough. I was hoping that the image is of something to which the breakthrough might apply. That being said, do you have any guidance as to what would be a better image? In other words an image of the type of encryption that the work relates to? Thanks in advance for any and all help.
joe - June 30, 2009 at 4:04 pm
Hi! (and greetings fellow CITP resident… at least a pre-greeting for when you arrive!)
Just to clarify, and I’m by no means an expert: homomorphic encryption is a neat type of encryption where a mathematical operation on the cyphertext (the encrypted stuff) translates to the same operation in the cleartext (the unencrypted data). So, if I encrypt a value like “1″ and then “add” the encrypted result to itself, when I decrypt the value will be “2″. In general, this should work for a set of operations, and I’m not sure the database example above is right (it depends on what one means by “query”).
Oh, and there’s no “image” that I can imagine for this… I guess a candidate would be one person locking something in a box, someone else performing something with the box to change it and the original person opening the new box to find something different inside… but that is not even close. I give up.
Steven M. Bellovin - June 30, 2009 at 5:29 pm
You’re quite correct about what homomorphic encryption is, but that form has been known for ~30 years, and is no more expensive than public key encryption. What’s new here is fully homomorphic encryption, where you can do multiplication as well as addition. My cryptotheoretician friends tell me it’s a tremendous theoretical achievement — but it may never be practical.
The scheme is based on something called “ideal lattices”. I have no idea what they are; my courses in that type of math were very long ago. That said, they’re a special form of lattice. I could explain them, but there’s not much point… (I did put a picture of a simple lattice at http://www.cs.columbia.edu/~smb/lattice.png — feel free to use it, but I have no idea if it’s an ideal lattice, nor do I know if it’s in any way related to the kinds of lattices used for this scheme.)
The best analogy I can give is Roman numerals. To a first approximation, any (reasonably small) number can be written that way. You can do arithmetic with them, and then translate the result back and get the proper answer. To someone who didn’t know the scheme, trying to understand why XXVII+XIX was XLVI would be rather difficult. (And efficiency? Imagine trying to do long division in Roman numerals!)
Database searching is one of the simpler things that can, in principle, be done with a fully homomorphic encryption scheme. There are many others; I’ll be happy to describe some, publicly or privately, if anyone is interested. Various forms of privacy-protecting searches are of great interest to various parts of the government — indeed, it’s one of my own research areas, funded by just such a part. Their interest is dual: they do indeed want to protect privacy, but a privacy-preserving scheme is also a more secure scheme, since if the database is compromised the attacker can learn much less.
As for the larger question — Deven is quite correct; one should never be sanguine. But the real reason to think about the issue is not this new development, but what’s already here…
Jens - July 1, 2009 at 7:34 am
Privacy-preserving data-mining? Take a look at the work of Professor Chris Clifton …
kswong - July 6, 2009 at 8:58 am
Hi All,
Is it possible for us to compare two ciphertexts encrypted with the same key without decryption?
joe - July 9, 2009 at 6:51 am
BTW, Schneier just wrote a brief article on this development: http://www.schneier.com/blog/archives/2009/07/homomorphic_enc.html
Leave a Reply