Paper 2024/115
Accelerating BGV Bootstrapping for Large $p$ Using Null Polynomials Over $\mathbb{Z}_{p^e}$
Abstract
The BGV scheme is one of the most popular FHE schemes for computing homomorphic integer arithmetic. The bootstrapping technique of BGV is necessary to evaluate arbitrarily deep circuits homomorphically. However, the BGV bootstrapping performs poorly for large plaintext prime $p$ due to its digit removal procedure exhibiting a computational complexity of at least $O(\sqrt{p})$. In this paper, we propose optimizations for the digit removal procedure with large $p$ by leveraging the properties of null polynomials over the ring $\mathbb{Z}_{p^e}$. Specifically, we demonstrate that it is possible to construct lowdegree null polynomials based on two observations of the input to the digit removal procedure: 1) the support size of the input can be upperbounded by $(2B+1)^2$; 2) the size of the lower digits to be removed can be upperbounded by $B$. Here $B$ can be controlled within a narrow interval $[22,23]$ in our parameter selection, making the degree of these null polynomials much smaller than $p$ for large values of $p$. These lowdegree null polynomials can significantly reduce the polynomial degrees during homomorphic digit removal, thereby decreasing both running time and capacity consumption. Theoretically, our optimizations reduce the computational cost of extracting a single digit from $O(\sqrt{pe})$ (by Chen and Han) or $O(\sqrt{p}\sqrt[4]{e})$ (by Geelen et al.) to $\min(2B+1,\sqrt{\lceil e/t\rceil(2B+1)})$ for some $t\ge 1$. We implement and benchmark our method on HElib with $p=17,127,257,8191$ and $65537$. With our optimized digit removal, we achieve a bootstrapping throughput $1.38\sim151$ times that in HElib, with the speedup increasing with the value of $p$. For $p=65537$, we accelerate the digit removal step by 80 times and reduce the bootstrapping time from more than 12 hours to less than 14 minutes.
Note: 2024.03.27  Fixed a mistake in Fig. 5
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2024
 Keywords
 BGVBootstrappingFHEHomomorphic Digit RemovalNull Polynomial
 Contact author(s)
 anyuwang @ tsinghua edu cn
 History
 20240327: last of 2 revisions
 20240126: received
 See all versions
 Short URL
 https://ia.cr/2024/115
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/115, author = {Shihe Ma and Tairong Huang and Anyu Wang and Xiaoyun Wang}, title = {Accelerating {BGV} Bootstrapping for Large $p$ Using Null Polynomials Over $\mathbb{Z}_{p^e}$}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/115}, year = {2024}, url = {https://eprint.iacr.org/2024/115} }