Cryptology ePrint Archive: Report 2017/079

Faster Bootstrapping of FHE over the Integers

Jung Hee Cheon and 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(\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.

Category / Keywords: public-key cryptography / Bootstrapping, Fully Homomorphic Encryption over the integers, CLT scheme, AES

Date: received 1 Feb 2017

Contact author: satanigh at snu ac kr

Available format(s): PDF | BibTeX Citation

Version: 20170206:190031 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]