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

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

##### Abstract

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 \tilde O}(\lambda^{10})$ which is too large for any practical system. In this paper we reduce the public key size to ${\cal \tilde O}(\lambda^{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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. An extended abstract will appear at CRYPTO 2011
Keywords
Fully Homomorphic Encryption
Contact author(s)
jean-sebastien coron @ uni lu
History
Short URL
https://ia.cr/2011/441

CC BY

BibTeX

@misc{cryptoeprint:2011/441,
author = {Jean-Sebastien Coron and Avradip Mandal and David Naccache and Mehdi Tibouchi},
title = {Fully Homomorphic Encryption over the Integers with Shorter Public Keys},
howpublished = {Cryptology ePrint Archive, Paper 2011/441},
year = {2011},
note = {\url{https://eprint.iacr.org/2011/441}},
url = {https://eprint.iacr.org/2011/441}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.