1. Homomorphic Lower Digits Removal and Improved FHE Bootstrapping 2018 Eurocrypt FHE PublicKeyEncryption
    Hao Chen and Kyoohyung Han
    [View PDF on eprint.iacr.org]
    [Show BibTex Citation]

    author = {Hao Chen and Kyoohyung Han},
    title = {Homomorphic Lower Digits Removal and Improved FHE Bootstrapping},
    howpublished = {Cryptology ePrint Archive, Report 2018/067},
    year = {2018},
    note = {\url{https://eprint.iacr.org/2018/067}},

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=l1(s) and the plaintext modulus is t=pr, we achieved bootstrapping depth logh+log(logp(ht)) in FV scheme. In case of the BGV scheme, we bring down the depth from logh+2logt to logh+logt.

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 Zpr. 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(257128) plaintext space with 128 slots. We also implemented our improved digit extraction procedure for the BGV scheme in HElib.