Paper 2014/032

Scale-Invariant Fully Homomorphic Encryption over the Integers

Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi

Abstract

At Crypto 2012, Brakerski constructed a scale-invariant fully homomorphic encryption scheme based on the LWE problem, in which the same modulus is used throughout the evaluation process, instead of a ladder of moduli when doing “modulus switching”. In this paper we describe a variant of the van Dijk et al. FHE scheme over the integers with the same scale-invariant property. Our scheme has a single secret modulus whose size is linear in the multiplicative depth of the circuit to be homomorphically evaluated, instead of exponential; we therefore construct a leveled fully homomorphic encryption scheme. This scheme can be transformed into a pure fully homomorphic encryption scheme using bootstrapping, and its security is still based on the Approximate-GCD problem. We also describe an implementation of the homomorphic evaluation of the full AES encryption circuit, and obtain significantly improved performance compared to previous implementations: about 23 seconds (resp. 3 minutes) per AES block at the 72-bit (resp. 80-bit) security level on a mid-range workstation. Finally, we prove the equivalence between the (error-free) decisional Approximate-GCD problem introduced by Cheon et al. (Eurocrypt 2013) and the classical computational Approximate-GCD problem. This equivalence allows to get rid of the additional noise in all the integer-based FHE schemes described so far, and therefore to simplify their security proof.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2014
Keywords
Fully Homomorphic EncryptionApproximage-GCDHomomorphic AES
Contact author(s)
jean-sebastien coron @ uni lu
History
2014-01-12: received
Short URL
https://ia.cr/2014/032
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/032,
      author = {Jean-Sébastien Coron and Tancrède Lepoint and Mehdi Tibouchi},
      title = {Scale-Invariant Fully Homomorphic Encryption over the Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2014/032},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/032}},
      url = {https://eprint.iacr.org/2014/032}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.