Paper 2024/164
Faster BGV Bootstrapping for Power-of-Two Cyclotomics through Homomorphic NTT
Abstract
Power-of-two cyclotomics is a popular choice when instantiating the BGV scheme because of its efficiency and compliance with the FHE standard. However, in power-of-two cyclotomics, the linear transformations in BGV bootstrapping cannot be decomposed into sub-transformations for acceleration with existing techniques. Thus, they can be highly time-consuming when the number of slots is large, degrading the advantage brought by the SIMD property of the plaintext space. By exploiting the algebraic structure of power-of-two cyclotomics, this paper derives explicit decomposition of the linear transformations in BGV bootstrapping into NTT-like sub-transformations, which are highly efficient to compute homomorphically. Moreover, multiple optimizations are made to evaluate homomorphic linear transformations, including modified BSGS algorithms, trade-offs between level and time, and specific simplifications for thin and general bootstrapping. We implement our method on HElib. With the number of slots ranging from 4096 to 32768, we obtain a 7.35x$\sim$143x improvement in the running time of linear transformations and a 4.79x$\sim$66.4x improvement in bootstrapping throughput, compared to previous works or the naive approach.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Fully Homomorphic EncryptionBGVBootstrappingNTT
- Contact author(s)
-
msh21 @ mails tsinghua edu cn
htr19 @ mails tsinghua edu cn
anyuwang @ tsinghua edu cn
xiaoyunwang @ tsinghua edu cn - History
- 2024-02-06: approved
- 2024-02-05: received
- See all versions
- Short URL
- https://ia.cr/2024/164
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/164, author = {Shihe Ma and Tairong Huang and Anyu Wang and Xiaoyun Wang}, title = {Faster BGV Bootstrapping for Power-of-Two Cyclotomics through Homomorphic NTT}, howpublished = {Cryptology ePrint Archive, Paper 2024/164}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/164}}, url = {https://eprint.iacr.org/2024/164} }