BGV/BFV Bootstrapping

Hi guys,

I’m currently investigating BGV/BFV bootstrapping.

It seems OpenFHE currently only supports CKKS bootstrapping. So, would BGV/BFV bootstrapping be included in future versions of OpenFHE?

Another thing I want to know is why BGV/BFV bootstrapping in the literature (Bootstrapping in Helib, etc) only provides a few packing slots. Normally, packing slots available in CKKS bootstrapping can be at most N/2, where N is the ring dimension, but BGV/BFV bootstrapping only has 128/64 slots. I’m wondering if that is the theoretical limit of BGV/BFV, or it was chosen to keep the bootstrapping algorithm simple or consume less multiplication depth?

Thanks in advance!

Correct. Currently, OpenFHE includes the implementation of CKKS bootstrapping only. We do have a prototype implementation of BGV that is under development. This will be announced in future releases of OpenFHE once BGV/BFV bootstrapping is completed. Note that, BGV and BFV bootstrappings are very similar, as already stated in the resources below.

In BFV/BGV, the number of slots depends on the plaintext modulus and the underlying cyclotomic ring used to instantiate the scheme. Both define the structure of the underlying plaintext algebra and Galois group. The limitations on the number of slots used are mainly due to performance, since the plaintext modulus and cyclotomic ring modulus have a huge impact on bootstrapping complexity.

Further details can be found in this work.
I also recommend reading the following works:

  1. Bootstrapping for HElib
  2. Fully Homomorphic Encryption with Polylog Overhead, in particular, Appendix C.
  3. Fully homomorphic SIMD operations

Minor correction. OpenFHE also supports bootstrapping for FHEW (DM) and TFHE (CGGI) schemes. In these schemes, (programmable) bootstrapping is a “primitive” operation.

BGV and BFV are the only schemes in OpenFHE that do not currently support bootstrapping, as @Caesar mentioned. We do have a prototype, but still quite a bit of work is needed to add the BGV/BFV bootstrapping to OpenFHE properly.

1 Like

Thank you for the informative reply!