High-Precision Homomorphic Modular Reduction for CKKS Bootstrapping

Cheon–Kim–Kim–Song (CKKS) scheme [9], a homomorphic encryption scheme enabling computation on encrypted real data without decryption, has been extensively researched to address data security challenges. The bootstrapping procedure in the CKKS scheme refreshes the noise that accumulates during homomorphic operations on a ciphertext, allowing the ciphertext to support more computations. Existing works attempt to reduce the bootstrapping error for enhancing the precision of the CKKS scheme by optimizing the polynomial-approximated modular function during bootstrapping. Hoever, due to the limitations of the approximation methods, achieving further approximation error reduction remains challenging. In this paper, we propose a method for achieving arbitrary precision bootstrapping for the CKKS scheme. First, we introduce a novel alternative function composed of an odd-degree sine series to represent the modular function. Then, we propose to apply the improved multi-interval Remez algorithm to approximate sine functions using polynomials and perform iteratively squaring operation to generate our sine series. Using our high-precision polynomial-approximated modular function, we implement bootstrapping with a lower error compared to existing work. Experimental results show that we reduce the bootstrapping error by 25% compared to [19] (EUROCRYPT’22). At the same level of error, we enable up to 2 ¹² slots during encoding while [19] only supports 2 ⁴ slots to obtain essentially no error, which highlight the practical advantages of our method. Moreover, our bootstrapping achieves both lower error and higher security than [21] (EUROCRYPT’21) and [18] (ePrint’20) since our key sparsity security parameter is higher.