[149004] in cryptography@c2.net mail archive
Re: [Cryptography] Advances in homomorphic encryption
daemon@ATHENA.MIT.EDU (Bear)
Sun Jan 12 15:23:12 2014
X-Original-To: cryptography@metzdowd.com
From: Bear <bear@sonic.net>
To: Christian Huitema <huitema@huitema.net>
Date: Sun, 12 Jan 2014 09:21:43 -0800
In-Reply-To: <08ab01cf0f44$b8d085e0$2a7191a0$@huitema.net>
Cc: 'Eric Mill' <eric@konklone.com>, 'Jonathan Katz' <jkatz@cs.umd.edu>,
'Landon Hurley' <ljrhurley@gmail.com>, cryptography@metzdowd.com
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
On Sat, 2014-01-11 at 19:16 -0800, Christian Huitema wrote:
> > cryptdb uses homomorphic encryption (as part of a larger system that leaks
> more information that "pure" HE would, but that is an
> > irrelevant tangent).
>
> 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. For example, we may want to find all the sales that
> happened last week and compute the average profit. That requires accessing
> the date field and verifying that it falls within last week's range. I
> can't see how to do that if the date is encrypted in a way that provides
> semantic security.
>
> -- Christian Huitema
This is true. Proof of "less than" is not simple. It winds up needing
to take the form of a zero-knowlege proof.
Of course there are other possibilities like discrete integral fields
for year, month, day, hour, minute, that could be checked quickly
in succession -- first by stepping through years looking for equality,
then months, then days, then hours, then minutes. You could figure
out whether a particular transaction is within a given date range by
making a relatively quick and simple series of equality checks.
Most other things you'd be interested in making comparisons about can
also be reduced to discrete integral fields.
Bear
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
