Paper 2025/1403

Faster Bootstrapping for CKKS with Less Modulus Consumption

Abstract

In fully homomorphic encryption, bootstrapping serves as a key component while also remaining the performance bottleneck of the scheme. Specifically, for CKKS bootstrapping, this bottleneck is reflected in significant computational overhead and modulus consumption. In this work, we improve the CKKS bootstrapping with lower time complexity and less modulus consumption. We first propose a novel rescaling operation, called level-conserving rescaling, that acts on CoeffsToSlots for saving moduli. Secondly, we reconstruct the rotation keys and merge the plaintext-ciphertext multiplication and rescaling operations into the key-switching procedure, which reduces the time complexity of matrix-vector multiplication for matrices with $\le$64 non-zero diagonals, albeit with increased space overhead. By combining the two methods in CoeffsToSlots in a non-trivial manner, we not only further accelerate the homomorphic linear transformations and save one level of moduli, but also reduce the total size of rotation keys. Experiments demonstrate the practicability of our techniques. Compared to the state of the art, our approaches save one level of moduli, achieving a $20\%\sim 35\%$ improvement in bootstrapping throughput and an 11.9\% $\sim$ 15.2\% reduction of rotation key size in CoeffsToSlots. Furthermore, with sufficient storage, our technology achieves up to 40\% higher bootstrapping throughput than before, at the cost of doubling the rotation key size in CoeffsToSlots. The bootstrapping precision and failure probability remain identical to the previous method.