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 \(\textsf{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 \(\textsf{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 \(\textsf{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 \(\textsf{CoeffsToSlots}\) . The bootstrapping precision and failure probability remain identical to the previous method.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Faster Bootstrapping for CKKS with Less Modulus Consumption

  • Lianglin Yan,
  • Pengfei Zeng,
  • Heyang Cao,
  • Peizhe Song,
  • Mingsheng Wang

摘要

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 \(\textsf{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 \(\textsf{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 \(\textsf{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 \(\textsf{CoeffsToSlots}\) . The bootstrapping precision and failure probability remain identical to the previous method.