Paper 2011/440

Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers

Jean-Sebastien Coron, David Naccache, and Mehdi Tibouchi

Abstract

We describe a compression technique that reduces the public key size of van Dijk, Gentry, Halevi and Vaikuntanathan's (DGHV) fully homomorphic scheme over the integers from \lambda^7 to \lambda^5. Our variant remains semantically secure, but in the random oracle model. We obtain an implementation of the full scheme with a 10.1 MB public key instead of 802 MB using similar parameters as in \cite{cmnt2011}. Additionally we show how to extend the quadratic encryption technique of \cite{cmnt2011} to higher degrees, to obtain a shorter public-key for the basic scheme. This paper also describes a new modulus switching technique for the DGHV scheme that enables to use the new FHE framework without bootstrapping from Brakerski, Gentry and Vaikuntanathan with the DGHV scheme. Finally we describe an improved attack against the Approximate GCD Problem on which the DGHV scheme is based, with complexity 2^\rho instead of 2^{3\rho/2}.

Note: Added extension of the Brakerski, Gentry and Vaikuntanathan new framework to the vDGHV scheme over the integers.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. An extended abstract of this paper appeared at Eurocrypt 2012. This is the full version.
Keywords
Fully Homomorphic Encryption
Contact author(s)
jean-sebastien coron @ uni lu
History
2012-01-18: last of 2 revisions
2011-08-15: received
See all versions
Short URL
https://ia.cr/2011/440
License
Creative Commons Attribution
CC BY

BibTeX

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