CTL
15 March 2011 - 15h00
Practical Fully-Homomorphic Encryption over the Integers
by Coron Jean-Sébastien from Université du Luxembourg
Résumé : At Eurocrypt 2010 van Dijk et al described a fully-homomorphic
encryption scheme over the integers. The main appeal of the scheme
(compared to Gentry's) was its conceptual simplicity; however with a
public key size k^10 for security parameter k the scheme looked
completely unpractical. In this talk we show how to reduce the public
key size down to k^5, and we describe a practical implementation of
the scheme.
Interestingly we obtain significantly better efficiency than the
recent Gentry-Halevi implementation of Gentry's scheme, despite using
very modest hardware. At the ``high'' security level, equivalent to
the ``large'' setting of Gentry-Halevi, we obtain encryption in about
3 minutes and a bootstrapping operation in about 5 minutes, while key
generation and decryption take negligible time. Public-key size is
also moderate: 250 MB at the ``high'' level (almost 10 times smaller
than Gentry-Halevi).
This shows that practical fully homomorphic encryption can be obtained
with a very simple scheme.
