EvalRound+ Bootstrapping and Its Rigorous Analysis for CKKS Scheme

Bootstrapping stands as a fundamental component of fully homomorphic encryption schemes. This work is aimed to significantly reduce the consumption of modulus in bootstrapping and increase the reservoir of modulus in general purpose, thereby enhancing the efficiency of fully homomorphic encryption performance, specifically for Cheon-Kim-Kim-Song scheme [Asiacrypt’17]. Kim et al. [Asiacrypt’22] suggested EvalRound bootstrapping which achieved remarkable reduction of modulus in CoeffToSlot, but there was the price to pay for the benefit. The consumption of modulus in SlotToCoeff was rather increased, and the increase in some cases amounts to invalidate the reduction. Our proposal, referred to as EvalRound<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup>, inherits the advantage of EvalRound bootstrapping in CoeffToSlot and resolved its disadvantage in SlotToCoeff. Through a set of rigorous and comprehensive analyses including causality tracing, momentum analysis and sparsity pattern, EvalRound<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup> bootstrapping achieved about 36% of modulus reductions in CoeffToSlot and SlotToCoeff compared to state-of-art bootstrapping suggested by Bossuat et al. [Eurocrypt’21] and about 35% compared to EvalRound bootstrapping in tests with commonly used parameter sets.