@inproceedings{chen2018homomorphic,
author = {Chen, Hao and Han, Kyoohyung},
title = {Homomorphic Lower Digits Removal and Improved FHE Bootstrapping},
booktitle = {EUROCRYPT 2018},
year = {2018},
month = {March},
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 applied a family of “lowest digit removal” polynomials to design an improved homomorphic digit extraction algorithm which is a crucial part in bootstrapping for both FV and BGV schemes. When the secret key has 1-norm h=||s||1
h=||s||1

and the plaintext modulus is t=pr

t=pr

, we achieved bootstrapping depth logh+log(logp(ht))

log⁡h+log⁡(logp⁡(ht))

in FV scheme. In case of the BGV scheme, we brought down the depth from logh+2logt

log⁡h+2log⁡t

to logh+logt

log⁡h+log⁡t

.
We implemented bootstrapping for FV in the SEAL library. We also introduced another “slim mode”, which restrict the plaintexts to batched vectors in ℤpr
Zpr

. The slim mode has similar throughput as the full mode, while each individual run is much faster and uses much smaller memory. For example, bootstrapping takes 6.75 s for vectors over GF(127) with 64 slots and 1381 s for vectors over GF(257128)

GF(257128)

with 128 slots. We also implemented our improved digit extraction procedure for the BGV scheme in HElib.},
url = {http://approjects.co.za/?big=en-us/research/publication/homomorphic-lower-digits-removal-and-improved-fhe-bootstrapping-3/},
}