Cryptographic Problem Solved (IBM and "fully homomorphic encryption")

You can also do things like with homomorphic encryption like private set intersections -- meaning that two people could see what's in the intersection of their private sets without revealing anything outside the intersection.

Gentry's work is still a long way away from being practical, but is an exciting theoretical result nonetheless.

A homomorphism is a mapping which preserves the structure of the original, where structure means the relationship between different parts. For example, x + y = z is a relationship between integers, that is preserved by map(i) = -i. For instance, 2 + 3 = 5, and -2 + -3 = -5.

BTW: the more common term isomorphism is a special case of homomorphism, in which you can always do the reverse mapping (technically, an isomorphism is a bijective homomorphism). Because it seems pointless to encrypt something if you can't decrypt it, I think the homomorphism in the article is actually an isomorphism. I think they say "homomorphism" because that is the specific aspect of the breakthrough.

Now, it seems that if you encrypt something in a way that preserves structure, it's not going to be very good encryption! Really excellent encryption seems more likely to look like a one-time pad. A one-time pad is when you have a book of unique random numbers, and you encrypt the message by using the message as an index into the book. For example, you can convert the string "hello world" into a number, and use that number as an index into the (very long) book, to find what unique number it refers to. You can then send that unique number to someone else who has the same book - they look it up backwards and get your message out. The encrypted message has no structural relationship to the unencrypted message. This is just one example of absence of structural relationship.

What these researchers claim is a way to encrypt a message in an effective way, which also preserves structure. Seems impossible, doesn't it?

OK, so what's the point? If you have preserved structure, then you can use tools that analyze structure, such as spam filtering. I tend to think that having the information about whether a message matches spam or not gives you an awful lot of information about the message... counter to the goal of encryption. So I'm withholding judgment... but I suspect that if they have solved this problem, they have done it partly by redefining the nature of the problem in a clever way.

http://en.wikipedia.org/wiki/NC_(complexity)

Is this old news?