Accelerating BGV Bootstrapping for Large p Using Null Polynomials over Z

Accelerating BGV Bootstrapping for Large p Using Null Polynomials over Z_(p~e)

扫码查看

原文链接

NETL
Springer Nature

外文摘要：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 homo-morphically. 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(p~(1/2)). In this paper, we propose optimizations for the digit removal procedure with large p by leveraging the properties of null polynomials over the ring Z_(p~e). Specifically, we demonstrate that it is possible to construct low-degree null polynomials based on two observations of the input to the digit removal procedure: 1) the support size of the input can be upper-bounded by (2B + 1)~2; 2) the size of the lower digits to be removed can be upper-bounded 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 low-degree 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(pe~(1/2)) (by Chen and Han) or O(p~(1/2)e~(1/4)) (by Gee-len et al.) to min(2B + 1,[e/t](2B + 1)~(1/2)) for some t≥ 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 ~ 151 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 h to less than 14min.

外文关键词：

BGVBootstrappingFHEHomomorphic Digit RemovalNull Polynomial

作者：

Shihe Ma、Tairong Huang、Anyu Wang、Xiaoyun Wang

展开 >

作者单位：

Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing, China

Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China

Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China##Zhongguancun Laboratory, Beijing, China##National Financial Cryptography Research Center, Beijing, China

Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China##Zhongguancun Laboratory, Beijing, China##National Financial Cryptography Research Center, Beijing, China##Shandong Institute of Blockchain, Jinan, China##Key Laboratory of Cryptologic Technology and Information Security (Ministry of Education), School of Cyber Science and Technology,Shandong University, Qingdao, China

展开 >

会议名称：

Annual International Conference on the Theory and Applications of Cryptographic Techniques

会议地点：

Zurich(CH)

会议母体文献：

Advances in Cryptology-EUROCRYPT 2024

页码：

403-432

出版时间：

2024

DOI：

10.1007/978-3-031-58723-8_14