Homomorphic encryption: Compute with data you cannot read | Hacker News Reader

Homomorphic encryption: Compute with data you cannot read

americanscientist.org

105 pointsfriism16 comments

The author, Brian Hayes, has an excellent blog at http://bit-player.org/ which is well worth following. Lots of posts about simple curiosities followed up much further than most people bother, and beautifully illustrated.

The post pointing to this American Scientist article adds “For crypto buffs, there’s an Easter egg in the first illustration.”

http://crypto.stanford.edu/craig/easy-fhe.pdf is a good summary of Craig Gentry's thesis (http://crypto.stanford.edu/craig/craig-thesis.pdf) and explains some of the limitations, for example why binary search in O(log n) time is not possible in a homomorphic scheme because it would necessarily reveal information about the untouched data.

I was trying to solve secure email at a mass scale, and the fundamental problems there were 1) key management and 2) spam.

We had a good solution for key management, but there was no way we felt we could give a way for scammers to appear more legit (hey, it came encrypted) without tools to fight it. The only way we would have had to solve it was either breaking security or through solid identity management, but that doesn't really (and probably cannot) exist across the Internet and is not necessarily what people are looking for in secure email.

That was when I discovered homomorphic encryption. It really would have been the solution to our problems (that, and how do I search my existing messages). Too bad we were 10 years early (or too poor to put the researchers to work for us :).

The other way to prevent spam is to hit 'em in the economics. If you require the sender put $1 in escrow, which the recipient can claim if it's spam (or, generally, not worth their time - but that'd be socially mediated), then you have changed things substantially.

Obligatory http://craphound.com/spamsolutions.txt

Re-reading my post, it sounds more "oh, it's simple" than I'd intended. I was just saying that there are potential approaches to cutting out spam other than filtering based on message content (which would be difficult-to-impossible in the case of encrypted email even with a good homomorphic encryption algorithm), and depending on exactly what the parent poster was trying to do they may (conceivably) be viable.

There are also proof-of-work solutions (as in, CPU time) along those lines. An analysis of that solution came to the conclusion it won't work as a standalone cure-all, but might be part of a more sophisticated overall scheme. (contact me for pointers if you're interested)

The problem with proof of work is that botnets have amongst the most work available.

What was the solution to key management? Just wondering what it looks like since the CA system doesn't work, and the GPG approach of key servers is too difficult for the laymen!

As for the spam issue, I am not sure that will ever get solved.

Printer friendly version http://www.americanscientist.org/issues/id.15906,y.2012,no.5...

That's a brilliant write-up. I'm still none the wiser what the evaluate function actually looks like, but he makes the rest seem simple enough to play around with.

Garbled circuits have been around for a long time. . . not sure if its new but it is a very interesting area.

Similiar Research in this area can be found by googling Secure Multiparty Computing. SMC or SMP

Fully homomorphic encryption reduces the communication necessary for MPC to a minimum. Since FHE is, at the moment, way too slow to be useful, work has gone in the direction of mixing classic techniques with somewhat homomorphic encryption, cf. http://eprint.iacr.org/2010/514 http://eprint.iacr.org/2011/535 http://eprint.iacr.org/2011/663

Doesn't it leak information?

If you know the algorithm (the evaluate function, if I understood correctly), you can make some assumptions about the data itself, even though you can't inspect the data you're operating on - e.g., exploiting the time it takes to compare password hashes [1].

[1] http://security.stackexchange.com/questions/9192/timing-atta...

What hardware makes this faster, SSE or the GPU?

Am I the only person who read the title of this as "Homoerotic erection"? I really hope not.

Reply on news.ycombinator.com