Comment by partition | Hacker News Reader

Comment by partition | Hacker News Reader

I have a question about homomorphic encryption and information leakage.

Do I have this right: A homomorphic encryption is a function

    e :: P -> C

between groups (P, -) and (C, +), where P is the set of plaintext and C is the set of gibberish and -, + are the respective group operations in either space, such that e is a homomorphism in the group theoretic sense?

Because if so, the following basic properties must hold:

    e(id_P) === id_C
    e(inv(p)) === inv(e(p))

Suppose you are a malicious cloud services provider and you are manipulating encrypted data. Couldn't you use these group properties to make much more informed observations about the encrypted data without ever having to decrypt it?

A very simple example: as a malicious cloud services provider, if you see a bunch of gibberish strings x, y1, y2 ... yn, and it turns out that x + y1 == y1, x + y2 == y2, ... x + yn == yn, wouldn't you at least have a sneaking suspicion, that x is the identity element? And in the situation where you could potentially make very damaging (to the other party) decisions based on this information, it would seem to defeat the purpose of homomorphic encryption.

Moreover, recall that the cloud services provider is technically also allowed to run any additional set of calculations using the group operation on the data you give it, not just those you provided. It seems that, in general, even with very unstructured data you could use the properties of homomorphisms to de-anonymize data very easily.

How is this issue addressed?

From what I remember from reading an ACM article on it a couple months back, you can also run the operations after they have been encrypted as well, preventing it a bit. I don't remember if there's a way to require encrypted operations, though.

In doing this, you could still brute-force operations and watch for statistically-significant results... but you'd have to guess at what valid operations are. Which amounts to the same problem as cracking the encryption in the first place, though it seems to me it would be an attack vector which weakens the encryption as a whole. To a significant degree? Don't know / doubt it.

Just don't ask me to explain the math of it. I don't know it, though I plan on studying enough to grasp it. Should take a few years.

edit: meh to the above.

Now that I've thought about it a bit longer, I do remember a decent chunk of the article dealing with information leakage, and how algorithms would need to be designed to touch as much information as possible (ideally, everything) to prevent leakage. So, it seems a map/reduce setup which combines all datapoints (removing unimportant ones further down the chain, thus hiding their influence) would be valuable.

OK, I should check out the ACM article.

It definitely seems like one needs to pare down the interactions with the provider to some bare minimum. Limiting it to single, uncorrelated map-reduce (or even just reduce) steps seems like it would remove a lot of potential for abuse.

But who knows---if service providers tend to take in and operate on more data than clients (especially from multiple clients), it seems there is a fundamental information imbalance, and obfuscating techniques by clients can't possibly do as well as deanonymizing techniques by the provider in the long run.

I wonder if it is the case that fully homomorphic encryption might _increase_ the potential for such information leakage relative to a partial homomorphic encryption; the more algebraic structures for which an encryption function is a homomorphism the more vulnerable it is. If a fully homomorphic encryption captures the +, * operations of a ring, you can exploit two identity elements, one for * and one for +. The next step in 'badness' would then be something like R-modules, where in addition to the ring you have another group (and another operation and identity element).

Reply on news.ycombinator.com