New Developments in Cryptography and Privacy

You may also like...

7 Responses

  1. 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:

    It is an awesome result — the first ever fully homomorphic encryption, a primitive that is *very* powerful for tons of applications (hence the hype), and something many believed is not possible (or at least very difficult to achieve). The only catch is, he succeeded to do this primitive with very computationally expensive crypto, so it’s not practical yet. In other words — the primitive itself has a ton of very practical applications.

    The primitive was implemented not efficiently enough.The hope is that this will inspire improvements and follow on work, now that we know it’s possible, that will make it practical. But there is a long way to go.

    (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…)

  2. Deven says:

    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.

  3. joe says:

    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. :)

  4. 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…

  5. Jens says:

    Privacy-preserving data-mining? Take a look at the work of Professor Chris Clifton …

  6. kswong says:

    Hi All,

    Is it possible for us to compare two ciphertexts encrypted with the same key without decryption?

  7. joe says:

    BTW, Schneier just wrote a brief article on this development: http://www.schneier.com/blog/archives/2009/07/homomorphic_enc.html