Welcome to the resource topic for 2018/067
Title:
Homomorphic Lower Digits Removal and Improved FHE Bootstrapping
Authors: Hao Chen, 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.
ePrint: https://eprint.iacr.org/2018/067
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .