Paper 2017/065

FHE Over the Integers: Decomposed and Batched in the Post-Quantum Regime

Daniel Benarroch, Zvika Brakerski, and Tancrède Lepoint


Fully homomorphic encryption over the integers (FHE-OI) is currently the only alternative to lattice-based FHE. FHE-OI includes a family of schemes whose security is based on the hardness of different variants of the approximate greatest common divisor (AGCD) problem. The majority of these works is based on the noise-free variant of AGCD which is potentially weaker than the general one. In particular, the noise-free variant relies on the hardness of factoring and is thus vulnerable to quantum attacks. A lot of effort was made to port techniques from second generation lattice-based FHE (using tensoring) to FHE-OI. Gentry, Sahai and Waters (Crypto 13) showed that third generation techniques (which were later formalized using the ``gadget matrix'') can also be ported. In this work, we propose a comprehensive study of applying third generation FHE techniques to the regime of FHE-OI. We present and analyze a third generation FHE-OI based on decisional AGCD without the noise-free assumption. We proceed to showing a batch version of our scheme where each ciphertext can encode a vector of messages and operations are performed coordinate-wise. We use a similar AGCD variant to Cheon et al.~(Eurocrypt 13) who suggested the batch approach for second generation FHE, but we do not require the noise-free component or a subset sum assumption. However, like Cheon et al., we do require circular security for our scheme, even for bounded homomorphism. Lastly, we discuss some of the obstacles towards efficient implementation of our schemes and discuss a number of possible optimizations.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2017
Contact author(s)
danielbenarroch92 @ gmail com
2017-02-06: revised
2017-01-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Benarroch and Zvika Brakerski and Tancrède Lepoint},
      title = {FHE Over the Integers: Decomposed and Batched in the Post-Quantum Regime},
      howpublished = {Cryptology ePrint Archive, Paper 2017/065},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.