## Fully Homomorphic Encryption over the
Integers with Shorter Public Keys

**Jean-Sebastien Coron, Avradip Mandal,
David Naccache, and Mehdi Tibouchi**

*
Université du Luxembourg;
Université du Luxembourg;
École normale supérieure; and
Université du Luxembourg +
Ecole normale supérieure
*
**Abstract.**
At Eurocrypt 2010 van Dijk *et al.* described a fully homomorphic
encryption scheme over the integers. The main appeal of this scheme
(compared to Gentry’s) is its conceptual simplicity. This simplicity comes
at the expense of a public key size in ~O(λ^{10}) which is too large for any
practical system. In this paper we reduce the public key size to ~O(λ^{7})
by encrypting with a quadratic form in the public key elements, instead
of a linear form. We prove that the scheme remains semantically secure,
based on a stronger variant of the approximate-GCD problem, already
considered by van Dijk *et al*.

We also describe the first implementation of the resulting fully homomorphic
scheme. Borrowing some optimizations from the recent Gentry-Halevi
implementation of Gentry’s scheme, we obtain roughly the same level
of eciency. This shows that fully homomorphic encryption can be
implemented using simple arithmetic operations.