Homomorphic Lower Digits Removal and Improved FHE Bootstrapping
EUROCRYPT 2018 |
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
and the plaintext modulus is
, we achieved bootstrapping depth
in FV scheme. In case of the BGV scheme, we brought down the depth from
We implemented bootstrapping for FV in the SEAL library. We also introduced another “slim mode”, which restrict the plaintexts to batched vectors in
. 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
with 128 slots. We also implemented our improved digit extraction procedure for the BGV scheme in HElib.