Homomorphic Lower Digits Removal and Improved FHE Bootstrapping

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 and the plaintext modulus is t = p r , we achieved bootstrapping depth log h + log(logp (ht)) in FV scheme. In case of the BGV scheme, we brought down the depth from log h + 2 log t to 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 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 seconds for vectors over GF(127) with 64 slots and 1381 seconds for vectors over GF(257128) with 128 slots. We also implemented our improved digit extraction procedure for the BGV scheme in HElib.