Cryptology ePrint Archive: Report 2018/067

Homomorphic Lower Digits Removal and Improved FHE Bootstrapping

Hao Chen and Kyoohyung Han

Abstract: Bootstrapping is a crucial operation in Gentry's breakthrough work on fully homomorphic encryption (FHE), where a homomorphic encryption scheme evaluates its own decryption algorithm. There has been a couple of implementations of bootstrapping, among which HElib arguably marks the state-of-the-art in terms of throughput, ciphertext/message size ratio and support for large plaintext moduli.

In this work, we apply a family of "lowest digit removal" polynomials to improve homomorphic digit extraction algorithm which is crucial part in bootstrapping for both FV and BGV schemes. If the secret key has 1-norm $h=l_1(s)$ and the plaintext modulus is $t = p^r$, we achieved bootstrapping depth $\log h + \log( \log_p(ht))$ in FV scheme. In case of the BGV scheme, we bring down the depth from $\log h + 2 \log t$ to $\log h + \log t$.

We implemented bootstrapping for FV in the SEAL library. Besides the regular mode, we introduce another "slim mode'", which restrict the plaintexts to batched vectors in $\mathbb{Z}_{p^r}$. The slim mode has similar throughput as the regular mode, while each individual run is much faster and uses much smaller memory. For example, bootstrapping takes $6.75$ seconds for 7 bit plaintext space with 64 slots and $1381$ seconds for $GF(257^{128})$ plaintext space with 128 slots. We also implemented our improved digit extraction procedure for the BGV scheme in HElib.

Category / Keywords: public-key cryptography / Fully Homomorphic Encryption; Bootstrapping

Original Publication (with minor differences): IACR-EUROCRYPT-2018

Date: received 15 Jan 2018, last revised 3 Feb 2018

Contact author: satanigh at snu ac kr

Available format(s): PDF | BibTeX Citation

Note: This paper is revised for the conference submission.

Version: 20180204:060821 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]