Paper 2018/067

Homomorphic Lower Digits Removal and Improved FHE Bootstrapping

Hao Chen and Kyoohyung Han


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.

Note: This paper is revised for the conference submission.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2018
Fully Homomorphic EncryptionBootstrapping
Contact author(s)
satanigh @ snu ac kr
2018-02-04: revised
2018-01-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hao Chen and Kyoohyung Han},
      title = {Homomorphic Lower Digits Removal and Improved {FHE} Bootstrapping},
      howpublished = {Cryptology ePrint Archive, Paper 2018/067},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.