International Association
for Cryptologic Research

CKKS bootstrapping requires a significant computational overhead and modulus consumption. In this work, we improve the homomorphic linear transformation algorithm 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 (Bossuat et al., Eurocrypt’21), our approaches: (1) increase the remaining homomorphic capacity, allowing fewer bootstrapping operations in large-depth circuit evaluation; (2) accelerate the CoeffsToSlots by a factor of 1.17$\sim$1.23 and reduce its rotation key size by 11.8$\%\sim$15.0$\%$. Furthermore, for better efficiency, we can speed up the fastest state-of-the-art bootstrapping scheme by 1.28 times at the cost of moderate additional space. The bootstrapping precision and failure probability remain identical to previous method.