Paper 2017/079

Faster Bootstrapping of FHE over the Integers

Jung Hee Cheon, Kyoohyung Han, and Duhyeong Kim


Bootstrapping in fully homomorphic encryption (FHE) over the integers is a homomorphic evaluation of the squashed decryption function suggested by van Dijk et al. The typical approach for the bootstrapping is representing the decryption function as a binary circuit with a fixed message space. All bootstrapping methods in FHEs over the integers use this approach; however, these methods require too many homomorphic multiplications, slowing down the whole procedure. In this paper, we propose an efficient bootstrapping method using various message spaces. Our bootstrapping method requires only $O(\log^{2}\lambda)$ number of homomorphic multiplications, which is significantly lower than $\tilde{O}(\lambda^{4})$ of the previous methods. We implement our bootstrapping method on the scale-invariant FHE over the integers; the CLT scheme introduced by Coron, Lepoint and Tibouchi. It takes 6 seconds for a 500-bit message space and a 72-bit security in PC. This is the fastest result among the bootstrapping methods on FHEs over the integers. We also apply our bootstrapping method to evaluate an AES-128 circuit homomorphically. As a result, it takes about 8 seconds per 128-bit block and is faster than the previous result of homomorphic evaluation of AES circuit using FHEs over the integers without bootstrapping.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
BootstrappingCLT schemeAES
Contact author(s)
satanigh @ snu ac kr
2017-02-06: received
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Kyoohyung Han and Duhyeong Kim},
      title = {Faster Bootstrapping of FHE over the Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2017/079},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.