Bootstrapping plays a critical role in fully homomorphic encryption (FHE) systems like BGV, BFV, and CKKS, enabling versatile leveled multiplication. While BGV and BFV utilize a digit extraction-based approach for bootstrapping, CKKS employs a scaled sine function to approximate the modular reduction operation, followed by homomorphic evaluation of sine functions using polynomials. This method introduces a fixed lower bound on approximation error. Rather than building on existing CKKS bootstrapping approaches, we propose an innovative alternative pathway that eliminates the need for sine function fitting in modular reduction approximation. Our method leverages BGV bootstrapping as a subroutine and introduces a ciphertext transformation technique to transform CKKS ciphertexts into BGV-compatible format, thereby enabling the integration of the BGV bootstrapping framework within the CKKS process. Such incorporation complements the existing result that BGV and BFV bootstrapping algorithms are equivalent and CKKS bootstrapping algorithm can serve as a subroutine in BFV bootstrapping algorithm. In addition, compared with the trivial way to construct a CKKS-subroutined BGV bootstrapping containing an intermediate transformation from BGV to BFV then to CKKS, we design a CKKS-subroutined BGV bootstrapping with a direct transformation. As a result, we point out the transformation among BGV, BFV and CKKS bootstrapping algorithms, enabling the optimization of each algorithm’s strengths and advantages.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A BGV-Subroutined CKKS Bootstrapping Algorithm Without Sine Approximation

  • Jingjing Fan,
  • Chi Zhang,
  • Zejiu Tan,
  • Zoe Lin Jiang,
  • Man Ho Au,
  • Siu Ming Yiu

摘要

Bootstrapping plays a critical role in fully homomorphic encryption (FHE) systems like BGV, BFV, and CKKS, enabling versatile leveled multiplication. While BGV and BFV utilize a digit extraction-based approach for bootstrapping, CKKS employs a scaled sine function to approximate the modular reduction operation, followed by homomorphic evaluation of sine functions using polynomials. This method introduces a fixed lower bound on approximation error. Rather than building on existing CKKS bootstrapping approaches, we propose an innovative alternative pathway that eliminates the need for sine function fitting in modular reduction approximation. Our method leverages BGV bootstrapping as a subroutine and introduces a ciphertext transformation technique to transform CKKS ciphertexts into BGV-compatible format, thereby enabling the integration of the BGV bootstrapping framework within the CKKS process. Such incorporation complements the existing result that BGV and BFV bootstrapping algorithms are equivalent and CKKS bootstrapping algorithm can serve as a subroutine in BFV bootstrapping algorithm. In addition, compared with the trivial way to construct a CKKS-subroutined BGV bootstrapping containing an intermediate transformation from BGV to BFV then to CKKS, we design a CKKS-subroutined BGV bootstrapping with a direct transformation. As a result, we point out the transformation among BGV, BFV and CKKS bootstrapping algorithms, enabling the optimization of each algorithm’s strengths and advantages.