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Õ(λ 10 ) which is too large for any practical system. In this paper we reduce the public key size toÕ(λ 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 efficiency. This shows that fully homomorphic encryption can be implemented using simple arithmetic operations.
In REF , Coron et al. reduce the size of the public key by using a similar but alternative encryption scheme.
Fully Homomorphic Encryption over the Integers with Shorter Public Keys
In P. Rogaway (Ed.), CRYPTO 2011, LNCS
Computer Science