Paper 2017/065

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

Daniel Benarroch, Zvika Brakerski, and Tancrède Lepoint

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2017
Keywords
FHEhomomorphicGSWDGHVpost-quantum
Contact author(s)
danielbenarroch92 @ gmail com
History
2017-02-06: revised
2017-01-31: received
See all versions
Short URL
https://ia.cr/2017/065
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/065,
      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{https://eprint.iacr.org/2017/065}},
      url = {https://eprint.iacr.org/2017/065}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.