[Cryptography] Advances in homomorphic encryption

[Eric Mill]

For anyone interested in the subject, I've found some more and better
resources.

Craig Gentry's original 2009 PhD thesis that theoretically solved fully
homomorphic encryption: http://crypto.stanford.edu/craig/craig-thesis.pdf

Bruce Schneier's analysis of Gentry's 2009 work, covering both its extreme
value and its then-current impracticality:
https://www.schneier.com/blog/archives/2009/07/homomorphic_enc.html

A second paper by Gentry, and Shai Halevi, from 2011 that outlines major
performance improvements: http://eprint.iacr.org/2010/520.pdf

IBM's very excited Dec 2013 announcement that they have a patent on the
work: http://www-03.ibm.com/press/us/en/pressrelease/42808.wss

It's neat that Gentry was able to keep the entropic noise level of repeated
homomorphic operations below a key threshold by running the decryption
algorithm itself in a homomorphic way against the ciphertext - a sort of
intermittent self-referential "refresh" operation to hold down the noise.
Pretty cool.

Also, I notice that this is premised on lattice-based cryptography, and so
the public keys are much larger than with the kind of cryptography used on
the web, in the order of many megabytes. That's an interesting twist when
thinking of web-scale deployment.

-- Eric


On Thu, Jan 9, 2014 at 11:40 AM, Eric Mill <eric at konklone.com> wrote:

> I am new-ish here and not a crypto expert (a mere web dev) - so please
> don't shred me. But! I've been hearing more about homomorphic
> encryption and it *sounds* really promising.
>
> Basically[1], that you can take two encrypted pieces of data, perform
> operations on them, and get an encrypted result that, when decrypted,
> has the result as if you performed that operation on the decrypted
> pieces. Data that is both manipulable and encrypted.
>
> So lots of people naturally see potential in making more
> privacy-oriented cloud services, that can perform computation for you
> without having access to your data. And the activity around it seems
> to be ramping up, like this paper[2] (which of course is not actually
> available to read, though the related works are):
>
> Poking around Github, I found one active, interesting library[3]
> that's focused on building out HE primitives. But it's very difficult
> for me to follow.
>
> Does anyone know about the state of affairs? Is this worth getting
> excited about?
>
> [1] http://en.wikipedia.org/wiki/Homomorphic_encryption
> [2]
> http://ecewp.ece.wpi.edu/wordpress/vernam/projects/homomorphic-encryption/
> [3] https://github.com/shaih/HElib
>
> Math:
> http://icsd.i2r.a-star.edu.sg/acns2012/slides/S9/Enhanced%20Flexibility%20for%20Homomorphic%20Encryption%20Schemes%20via%20CRT.pdf
> Slight math:
> http://cps-vo.org/bitcache/a76d514fb1c214a13635394baf6df05355c1f243?vid=15128&disposition=inline&op=view
>
> -- Eric
>
> https://konklone.com
> https://twitter.com/konklone
>



-- 
konklone.com | @konklone <https://twitter.com/konklone>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140110/93000db8/attachment.html>