Paper 2011/441

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.

Metadata
Available format(s)
PDF
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
2011-08-15: received
Short URL
https://ia.cr/2011/441
License
Creative Commons Attribution
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.