EvalComp: Bootstrapping Based on Homomorphic Comparison Function for CKKS

The Approximate Homomorphic Encryption scheme CKKS offers a distinctive and effective approach to privacy-preserving computation, with significant potential applications in IoT and machine learning domains. Recent advancements have introduced bootstrapping techniques tailored for CKKS, including the EvalMod and EvalRound bootstrapping techniques. These bootstrapping techniques mainly focus on approximate computation of modular reduction functions. However, the approximation of modular functions encounters challenges related to computational efficiency and bootstrapping precision, thus emerging as a major bottleneck in the advancement of bootstrapping techniques. Motivated by these concerns, in this paper, we introduce a novel bootstrapping scheme named EvalComp, which eliminates the need to fit modular functions. Unlike existing approaches, EvalComp constructs a homomorphic rounding function using the Homomorphic Comparison Function (HCF) and thus removes the integer multiples of the modulus <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\boldsymbol {q}$ </tex-math></inline-formula> from the ciphertext. For <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\boldsymbol {N = {2^{9}}}$ </tex-math></inline-formula>, EvalComp enhances bootstrapping precision by over 11 bits and computational efficiency by 16.7% compared with the latest EvalMod scheme (JM22). Additionally, compared with the EvalRound scheme (KPK22+), our scheme improves bootstrapping precision by 2-3 bits and computational efficiency by 20.2%. According to the bootstrapping performance comparison criterion, the performance of EvalComp achieves 1.80 times that of JM22 and 1.69 times that of KPK22+.