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 2.4x$\sim$55.1x improvement in bootstrapping throughput, compared to previous works or the naive approach.

Note: 2024.10.03 - Update to the Asiacrypt 2024 final version - Fix an implementation problem identified by Mr. Robin Geelen - Include benchmark results with non-double-CRT linear transformation constants - Include SlotToCoeff-first optimization and its benchmark results - Adjust the calculation of the time&capacity consumption of unpacking&repacking in general bootstrapping