Paper 2017/079

Faster Bootstrapping of FHE over the Integers

Jung Hee Cheon, Kyoohyung Han, and Duhyeong Kim

Abstract

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(log2λ) number of homomorphic multiplications, which is significantly lower than 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
BootstrappingCLT schemeAES
Contact author(s)
satanigh @ snu ac kr
History
2017-02-06: received
Short URL
https://ia.cr/2017/079
License
Creative Commons Attribution
CC BY

BibTeX

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