Fully Homomorphic Encryption over the Integers with Shorter Public Keys
At Eurocrypt 2010 van Dijk sl 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 cal ˜ O(λ10) which is too large for any practical system. In this paper we reduce the public key size to cal ˜ 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 sl 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.
Avradip Mandal is a PhD student at University of Luxembourg, Luxembourg under the supervision of Jean-Sebastien Coron. Currently he is an intern at eXtreme Computing Group, Microsoft Research with Lan Nguyen as his mentor. Before he obtained M.Math and B.Tech from University of Waterloo, Canada and Indian Institute of Technology Kharagpur, India respectively.
- Avradip Mandal
- University of Luxembourg