OverModRaise: Reducing Modulus Consumption of CKKS Bootstrapping

The Cheon-Kim-Kim-Song (CKKS) homomorphic encryption scheme is widely adopted for securely evaluating circuits over real numbers, such as those arising in privacy-preserving machine learning (PPML), because it efficiently supports approximate floating-point arithmetic of messages. A CKKS ciphertext has a finite level, which corresponds to the budget for how many multiplicative operations can be applied. Once these levels are consumed, the ciphertext must be refreshed through a bootstrapping procedure to restore its capacity for further computation. The CKKS bootstrapping procedure consists of four main steps: 1) ModRaise, which raises the ciphertext coefficient modulus; 2) C2S, which homomorphically evaluates the inverse-DFT (iDFT) to enable further operations on the ciphertext coefficients; 3) EvalMod, which homomorphically removes the unintended coefficients introduced by ModRaise and shifted to the message side by C2S; and 4) S2C, which homomorphically evaluates the DFT to map the ciphertext back from the iDFT domain. However, these bootstrapping procedures also consume a significant number of levels, leaving fewer levels after each bootstrapping. In this work, we introduce three techniques—OverModRaise1, OverModRaise2, and Tuple-C2S/S2C—that target reductions in the modulus consumption of C2S/S2C among the CKKS bootstrapping procedures, without introducing substantial overhead or compromising security. By combining these techniques, our implementation demonstrates at most 41% throughput improvement compared to the state-of-the-art bootstrapping.