[148985] in cryptography@c2.net mail archive
Re: [Cryptography] Advances in homomorphic encryption
daemon@ATHENA.MIT.EDU (Eric Mill)
Fri Jan 10 11:41:25 2014
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <CANBOYLWb+0z=Z1+z_7c-WBj4qtP+5u6L1evcBHM3dqZ5n4XbwA@mail.gmail.com>
From: Eric Mill <eric@konklone.com>
Date: Fri, 10 Jan 2014 01:42:26 -0500
To: "cryptography@metzdowd.com List" <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============3330354739817614285==
Content-Type: multipart/alternative; boundary=089e01538848e3797204ef98096e
--089e01538848e3797204ef98096e
Content-Type: text/plain; charset=ISO-8859-1
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@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>
--089e01538848e3797204ef98096e
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">For anyone interested in the subject, I've found some =
more and better resources.<div><br></div><div>Craig Gentry's original 2=
009 PhD thesis that theoretically solved fully homomorphic encryption:=A0<a=
href=3D"http://crypto.stanford.edu/craig/craig-thesis.pdf" target=3D"_blan=
k">http://crypto.stanford.edu/craig/craig-thesis.pdf</a><br>
</div><div><br></div><div>Bruce Schneier's analysis of Gentry's 200=
9 work, covering both its extreme value and its then-current impracticality=
:=A0<a href=3D"https://www.schneier.com/blog/archives/2009/07/homomorphic_e=
nc.html" target=3D"_blank">https://www.schneier.com/blog/archives/2009/07/h=
omomorphic_enc.html</a></div>
<div><br></div><div>A second paper by Gentry, and Shai Halevi, from 2011 th=
at outlines major performance improvements:=A0<a href=3D"http://eprint.iacr=
.org/2010/520.pdf" target=3D"_blank">http://eprint.iacr.org/2010/520.pdf</a=
></div>
<div><br></div>
<div>IBM's very excited Dec 2013 announcement that they have a patent o=
n the work:=A0<a href=3D"http://www-03.ibm.com/press/us/en/pressrelease/428=
08.wss" target=3D"_blank">http://www-03.ibm.com/press/us/en/pressrelease/42=
808.wss</a></div>
<div>
<br></div><div>It's neat that Gentry was able to keep the entropic nois=
e level of repeated homomorphic operations below a key threshold by running=
the decryption algorithm itself in a homomorphic way against the ciphertex=
t - a sort of intermittent self-referential "refresh" operation t=
o hold down the noise. Pretty cool.</div>
<div><br></div><div>Also, I notice that this is premised on lattice-based c=
ryptography, and so the public keys are much larger than with the kind of c=
ryptography used on the web, in the order of many megabytes. That's an =
interesting twist when thinking of web-scale deployment.</div>
<div><br></div><div>-- Eric</div><div class=3D"gmail_extra"><br><br><div cl=
ass=3D"gmail_quote">On Thu, Jan 9, 2014 at 11:40 AM, Eric Mill <span dir=3D=
"ltr"><<a href=3D"mailto:eric@konklone.com" target=3D"_blank">eric@konkl=
one.com</a>></span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">I am new-ish here and not a crypto expert (a=
mere web dev) - so please<br>
don't shred me. But! I've been hearing more about homomorphic<br>
encryption and it *sounds* really promising.<br>
<br>
Basically[1], that you can take two encrypted pieces of data, perform<br>
operations on them, and get an encrypted result that, when decrypted,<br>
has the result as if you performed that operation on the decrypted<br>
pieces. Data that is both manipulable and encrypted.<br>
<br>
So lots of people naturally see potential in making more<br>
privacy-oriented cloud services, that can perform computation for you<br>
without having access to your data. And the activity around it seems<br>
to be ramping up, like this paper[2] (which of course is not actually<br>
available to read, though the related works are):<br>
<br>
Poking around Github, I found one active, interesting library[3]<br>
that's focused on building out HE primitives. But it's very difficu=
lt<br>
for me to follow.<br>
<br>
Does anyone know about the state of affairs? Is this worth getting<br>
excited about?<br>
<br>
[1] <a href=3D"http://en.wikipedia.org/wiki/Homomorphic_encryption" target=
=3D"_blank">http://en.wikipedia.org/wiki/Homomorphic_encryption</a><br>
[2] <a href=3D"http://ecewp.ece.wpi.edu/wordpress/vernam/projects/homomorph=
ic-encryption/" target=3D"_blank">http://ecewp.ece.wpi.edu/wordpress/vernam=
/projects/homomorphic-encryption/</a><br>
[3] <a href=3D"https://github.com/shaih/HElib" target=3D"_blank">https://gi=
thub.com/shaih/HElib</a><br>
<br>
Math: <a href=3D"http://icsd.i2r.a-star.edu.sg/acns2012/slides/S9/Enhanced%=
20Flexibility%20for%20Homomorphic%20Encryption%20Schemes%20via%20CRT.pdf" t=
arget=3D"_blank">http://icsd.i2r.a-star.edu.sg/acns2012/slides/S9/Enhanced%=
20Flexibility%20for%20Homomorphic%20Encryption%20Schemes%20via%20CRT.pdf</a=
><br>
Slight math: <a href=3D"http://cps-vo.org/bitcache/a76d514fb1c214a13635394b=
af6df05355c1f243?vid=3D15128&disposition=3Dinline&op=3Dview" target=
=3D"_blank">http://cps-vo.org/bitcache/a76d514fb1c214a13635394baf6df05355c1=
f243?vid=3D15128&disposition=3Dinline&op=3Dview</a><br>
<br>
-- Eric<br>
<br>
<a href=3D"https://konklone.com" target=3D"_blank">https://konklone.com</a>=
<br>
<a href=3D"https://twitter.com/konklone" target=3D"_blank">https://twitter.=
com/konklone</a><br>
</blockquote></div><br><br clear=3D"all"><div><br></div>-- <br><div dir=3D"=
ltr"><div><a href=3D"http://konklone.com" target=3D"_blank">konklone.com</a=
> | <a href=3D"https://twitter.com/konklone" target=3D"_blank">@konklone</a=
><br></div>
</div>
</div></div>
--089e01538848e3797204ef98096e--
--===============3330354739817614285==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============3330354739817614285==--
