[148983] in cryptography@c2.net mail archive
Re: [Cryptography] Advances in homomorphic encryption
daemon@ATHENA.MIT.EDU (Jonathan Katz)
Thu Jan 9 22:34:09 2014
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <51c98ea1-62c5-4f1c-8746-833a32db30a2@email.android.com>
Date: Thu, 9 Jan 2014 21:12:59 -0500
From: Jonathan Katz <jkatz@cs.umd.edu>
To: Landon Hurley <ljrhurley@gmail.com>
X-CSD-MailScanner-From: jkatz@cs.umd.edu
Cc: "cryptography@metzdowd.com List" <cryptography@metzdowd.com>,
Eric Mill <eric@konklone.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============3506867566353450594==
Content-Type: multipart/alternative; boundary=047d7ba97356dccf7e04ef944373
--047d7ba97356dccf7e04ef944373
Content-Type: text/plain; charset=ISO-8859-1
On Thu, Jan 9, 2014 at 2:11 PM, Landon Hurley <ljrhurley@gmail.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
>
>
> Eric Mill <eric@konklone.com> wrote:
> >
> >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?
> >
> For what it's worth, a group at MIT seems to be actively developing
> cryptdb, which is an SQL implementation that emulates homomorphic
> encryption. There's a mailing list that, up until I unsubscribed, had a low
> S/N ratio, but that had seemed to be changing. As such, it may be an
> interesting place to get implementation advice.
>
It's important to distinguish between homomorphic encryption and *fully*
homomorphic encryption. (Unfortunately, even the academic literature has
begun using the terms carelessly.) The former goes back ~35 years, can be
roughly as efficient as standard public-key crypto, but only supports
(essentially) *addition* of encrypted values. The latter goes back ~5
years, is orders of magnitude less efficient than standard public-key
crypto, and supports arbitrary computations on encrypted data.
cryptdb uses homomorphic encryption (as part of a larger system that leaks
more information that "pure" HE would, but that is an irrelevant tangent).
> Google brings up a list of academic papers on the design itself (I seem to
> recall it starting as dissertation work) so that may be helpful as well.
>
> hth,
> landon
>
> >[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
>
>
> - --
> Violence is the last refuge of the incompetent.
> -----BEGIN PGP SIGNATURE-----
> Version: APG v1.0.9
>
> iQJBBAEBCgArBQJSzvR9JBxMYW5kb24gSHVybGV5IDxsanJodXJsZXlAZ21haWwu
> Y29tPgAKCRA3qYf9H1SVrMHKD/9kp4arzj1uP3t5+SHnybDPYjsdk6Qc/cMo7sLv
> uSwz31bmyrvyxP1o79kc38M9bkZZk7QrfTD1KL9sQrfl33lIPT6JGWBCWSDZwl//
> tBMPaJ03TpT+S8ptRKq54nrOmEnCugiQTYA1+VGKAn19ejvg3TNUjzkRFbQZwU4g
> Z4WyS3js4Ly/qrARtv1E5D1k3ML1jHoHChzvphn62/QeeehmqPpvg7E21ihQYNMs
> fVau4vKDK0JMncy8NUSFbdR5qKvCfy8zcwC28t1cZ0BmOBt4g4fnFCL3JHQBQz1T
> j+tcRCpHj/WnnVVIDw8EtgbrgmAIA33NL6+I/IA95nKgMJXJ0m1VkP64rpArhC8T
> ciSeXYb4UZ1nxsBsfU7rktkFN5v+K/lG56VuM2v+fDOhrMwKIuSwKiJpjLdywTFu
> wxBJKvGKpDxL2+EmirGwZnMZzMeMzQ2IQo1Nlplj/UjIns3andhdHPlfzMZgJVn6
> 4ZXSUYegsfJrJM6PZtfAjQK0V+2PCiYY5F/8lAxzoVNms8bDYMFyMtFLf3k71Y67
> YP2N35VLxD/fU5z0eu/g2jdFVshzR19ScJbRu3Rfk/5r2nU9+IMQXR8oFCqS7bqi
> iKl5YxKLpicJDzFDfg/r46e44G7H2hY9/gSa52ItY2/I9r2Y9ZN+g1E/o6TPvpOb
> dcaBqg==
> =cDp8
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> The cryptography mailing list
> cryptography@metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
>
>
--047d7ba97356dccf7e04ef944373
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Thu, Jan 9, 2014 at 2:11 PM, Landon Hurley <span dir=3D=
"ltr"><<a href=3D"mailto:ljrhurley@gmail.com" target=3D"_blank">ljrhurle=
y@gmail.com</a>></span> wrote:<br><div class=3D"gmail_extra"><div class=
=3D"gmail_quote">
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">-----BEGIN PGP SIGNED MESSAGE-----<br>
Hash: SHA512<br>
<div class=3D"im"><br>
<br>
<br>
Eric Mill <<a href=3D"mailto:eric@konklone.com">eric@konklone.com</a>>=
; wrote:<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 dif=
ficult<br>
>for me to follow.<br>
><br>
>Does anyone know about the state of affairs? Is this worth getting<br>
>excited about?<br>
><br>
</div>For what it's worth, a group at MIT seems to be actively developi=
ng cryptdb, which is an SQL implementation that emulates homomorphic encryp=
tion. There's a mailing list that, up until I unsubscribed, had a low S=
/N ratio, but that had seemed to be changing. As such, it may be an interes=
ting place to get implementation advice.<br>
</blockquote><div><br></div><div>It's important to distinguish between =
homomorphic encryption and *fully* homomorphic encryption. (Unfortunately, =
even the academic literature has begun using the terms carelessly.) The for=
mer goes back ~35 years, can be roughly as efficient as standard public-key=
crypto, but only supports (essentially) *addition* of encrypted values. Th=
e latter goes back ~5 years, is orders of magnitude less efficient than sta=
ndard public-key crypto, and supports arbitrary computations on encrypted d=
ata.<br>
<br></div><div>cryptdb uses homomorphic encryption (as part of a larger sys=
tem that leaks more information that "pure" HE would, but that is=
an irrelevant tangent).<br></div><div>=A0</div><blockquote class=3D"gmail_=
quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1=
ex">
Google brings up a list of academic papers on the design itself (I seem to =
recall it starting as dissertation work) so that may be helpful as well.<br=
>
<br>
hth,<br>
landon<br>
<div class=3D"im"><br>
>[1] <a href=3D"http://en.wikipedia.org/wiki/Homomorphic_encryption" tar=
get=3D"_blank">http://en.wikipedia.org/wiki/Homomorphic_encryption</a><br>
>[2]<br>
><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:=
//github.com/shaih/HElib</a><br>
><br>
>Math:<br>
><a href=3D"http://icsd.i2r.a-star.edu.sg/acns2012/slides/S9/Enhanced%20=
Flexibility%20for%20Homomorphic%20Encryption%20Schemes%20via%20CRT.pdf" tar=
get=3D"_blank">http://icsd.i2r.a-star.edu.sg/acns2012/slides/S9/Enhanced%20=
Flexibility%20for%20Homomorphic%20Encryption%20Schemes%20via%20CRT.pdf</a><=
br>
>Slight math:<br>
><a href=3D"http://cps-vo.org/bitcache/a76d514fb1c214a13635394baf6df0535=
5c1f243?vid=3D15128&disposition=3Dinline&op=3Dview" target=3D"_blan=
k">http://cps-vo.org/bitcache/a76d514fb1c214a13635394baf6df05355c1f243?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://twit=
ter.com/konklone</a><br>
<br>
<br>
</div>- --<br>
Violence is the last refuge of the incompetent.<br>
-----BEGIN PGP SIGNATURE-----<br>
Version: APG v1.0.9<br>
<br>
iQJBBAEBCgArBQJSzvR9JBxMYW5kb24gSHVybGV5IDxsanJodXJsZXlAZ21haWwu<br>
Y29tPgAKCRA3qYf9H1SVrMHKD/9kp4arzj1uP3t5+SHnybDPYjsdk6Qc/cMo7sLv<br>
uSwz31bmyrvyxP1o79kc38M9bkZZk7QrfTD1KL9sQrfl33lIPT6JGWBCWSDZwl//<br>
tBMPaJ03TpT+S8ptRKq54nrOmEnCugiQTYA1+VGKAn19ejvg3TNUjzkRFbQZwU4g<br>
Z4WyS3js4Ly/qrARtv1E5D1k3ML1jHoHChzvphn62/QeeehmqPpvg7E21ihQYNMs<br>
fVau4vKDK0JMncy8NUSFbdR5qKvCfy8zcwC28t1cZ0BmOBt4g4fnFCL3JHQBQz1T<br>
j+tcRCpHj/WnnVVIDw8EtgbrgmAIA33NL6+I/IA95nKgMJXJ0m1VkP64rpArhC8T<br>
ciSeXYb4UZ1nxsBsfU7rktkFN5v+K/lG56VuM2v+fDOhrMwKIuSwKiJpjLdywTFu<br>
wxBJKvGKpDxL2+EmirGwZnMZzMeMzQ2IQo1Nlplj/UjIns3andhdHPlfzMZgJVn6<br>
4ZXSUYegsfJrJM6PZtfAjQK0V+2PCiYY5F/8lAxzoVNms8bDYMFyMtFLf3k71Y67<br>
YP2N35VLxD/fU5z0eu/g2jdFVshzR19ScJbRu3Rfk/5r2nU9+IMQXR8oFCqS7bqi<br>
iKl5YxKLpicJDzFDfg/r46e44G7H2hY9/gSa52ItY2/I9r2Y9ZN+g1E/o6TPvpOb<br>
dcaBqg=3D=3D<br>
=3DcDp8<br>
-----END PGP SIGNATURE-----<br>
<div class=3D"HOEnZb"><div class=3D"h5"><br>
_______________________________________________<br>
The cryptography mailing list<br>
<a href=3D"mailto:cryptography@metzdowd.com">cryptography@metzdowd.com</a><=
br>
<a href=3D"http://www.metzdowd.com/mailman/listinfo/cryptography" target=3D=
"_blank">http://www.metzdowd.com/mailman/listinfo/cryptography</a><br>
<br>
</div></div></blockquote></div><br></div></div>
--047d7ba97356dccf7e04ef944373--
--===============3506867566353450594==
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
--===============3506867566353450594==--
