[Cryptography] Advances in homomorphic encryption

[Adam Back]

On Sat, Jan 11, 2014 at 07:16:43PM -0800, Christian Huitema wrote:
>Homomorphic encryption enables computations using additions and
>multiplications, but I wonder about the domain of application. Whether you
>consider projection and joint in a SQL database, or map/reduce, we need to
>perform comparisons. 

So cryptdb is mostly using encrypted search (think deterministic or
convergent encryption, encrypted search terms, encrypted indexes) like
Wagner et al's original paper, but with various relaxations and extensions.. 
Cryptdb model for selective security relacation is there are different
encryptions, and if the querier needs to do some more advanced query he
releases keys allowing a more flexible but less secure search.  Their main
result is that surprisingly you can execute most of SQL by doing that. 
Homomorphic addition is one of the modes, though the rest are all symmetric
constructs.

You maybe familiar with OPE order-preserving (symmetric) encryption (for
comparisons).  Its definitely short of semantic security, that you
mentioned, its significantly weak if used in a context with ability to use
it adapativly against an oracle (the database).

Its just what you can do now, practically; if/and until someone manages to
make FHE practically efficient.  I think the original poster of this thread
said "order of magintude slower" I think that is a gross understatement, I
believe its more like "7 or 8 orders of magnitude slower".  But then I didnt
keep up with the latest benchmark and optimization papers.  They could
really do with a standarized benchmark like time to compute one block of
SHA256, on a common desktop/server CPU.  I mean I'd take practical latency
on a 1000 GPU cluster as an interesting step, i think we're still many
orders of magnitude out from that.  Be interested in corrections if I am
over stating that.

I am not nay saying FHE, I think it has paradigm changing possibilities.  It
allows many of the things that the trustworthy computing system can do up to
hardware tamper assurance and manufacturer certification trust, but with end
to end security for the person with the keys.  Just trying to point out the
distance from here and practicality.

Adam