BGV Bootstrapping

[sp18]

Hi! Could anyone link to the bootstrap algorithm paper for BGV based FHE?

[Caesar]

These are good resources on BGV bootstrapping:

1. Bootstrapping for HElib
2. Homomorphic Lower Digits Removal and Improved FHE Bootstrapping
3. Bootstrapping for BGV and BFV Revisited

[sp18]

Thanks a lot. That’s very helpful

[ypolyakov]

There are several newer papers, too, with more efficient BGV/BFV bootstrapping designs:

• Simpler and Faster BFV Bootstrapping for Arbitrary Plaintext Modulus from CKKS
• Accelerating BGV Bootstrapping for Large $p$ Using Null Polynomials Over $\mathbb{Z}_{p^e}$
• Relaxed Functional Bootstrapping: A New Perspective on BGV/BFV Bootstrapping
• Revisiting the Slot-to-Coefficient Transformation for BGV and BFV
• Faster BGV Bootstrapping for Power-of-Two Cyclotomics through Homomorphic NTT

[sp18]

Thank you so much! Was curious to know if any of the above bootstrapping schemes have been implemented in openFHE yet in any of the examples?

[ypolyakov]

There was an old limited implementation in PALISADE, but nothing in OpenFHE, to the best of my knowledge. We do not believe these algorithms are practical enough, as compared to CKKS or FHEW/TFHE bootstrapping.