Small interval interpolation fitting bootstrapping method based on residue number system

基于余数系统的小间隔插值拟合自举方法

¹ School of Computer Science, Northwestern Polytechnical University, Xi'an 710072, China
² School of Software, Northwestern Polytechnical University, Xi'an 710072, China
³ School of Life Science and Technology, Xidian University, Xi'an 710071, China

Received: 25 September 2023

Abstract

Aiming at the problem that the bootstrapping time of approximate homomorphic encryption scheme is too long, a small interval interpolation fitting method based on residue system is proposed. In this paper, the sinusoidal function by using interpolating and fitting method between the multiple cells to avoid the increase in bootstrapping time or decrease in calculation accuracy caused by the high degree of fitting polynomial is calculated. And the efficiency of modular multiplication and modular inversion in the calculation process is improved by combining the residual system. Lagrange interpolation polynomial is used to interpolate and fit the sine function among different intervals. The comparison function is implemented by the compound implementation of low-degree polynomials, and an interval judgment algorithm is proposed to identify the interval of the ciphertext. Finally, under the precision of 24 bits, the modular operation time in the bootstrapping process decreased to 8% of the HEAAN. When the number of slots is 65 536, the average module operation time per slot is 0.028 ms.

摘要

针对近似同态加密方案自举耗时过大的问题提出了一种基于余数系统的小区间插值拟合自举方法。通过在多个小区间内对模函数进行插值拟合避免因拟合多项式次数过高产生自举时间过长或计算精度降低的问题, 并通过结合余数系统提高计算过程中模乘运算的模逆运算效率。选用拉格朗日插值多项式对小区间内的正弦函数进行插值拟合。通过多个低次多项式复合计算实现比较函数, 并提出了一种区间判断算法来识别密文所在区间。最终在24比特精度下, 同态计算过程中模运算耗时下降到HEAAN库的8%, 在计算槽的数量为65 536时, 平均每槽的模运算时间为0.028 ms。