Homomorphic Modular Reduction and Improved Bootstrapping for BGV Scheme

The chapter delves into the critical aspect of bootstrapping in fully homomorphic encryption (FHE), focusing on the BGV scheme. It introduces a new homomorphic modular reduction algorithm inspired by the 'blind rotation' technique, significantly enhancing the efficiency and noise performance of the bootstrapping procedure. This algorithm is designed to work with RLWE-based HE schemes, including the BGV scheme, and is shown to achieve polynomial noise growth. The chapter also provides a detailed analysis of the computational complexity and noise accumulation, demonstrating that the proposed method outperforms existing techniques in terms of both efficiency and security assumptions. The improvements made in this chapter not only advance the practicality of FHE but also offer valuable insights for other applications requiring homomorphic modular reduction.