[Cryptography] Advances in homomorphic encryption

[Bear]

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