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

Small interval interpolation fitting bootstrapping method based on residue number system

作　　者：李慧贤[1] 王富磊 沈春 刘诗源 庞辽军 LI Huixian;WANG Fulei;SHEN Chun;LIU Shiyuan;PANG Liaojun(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)

机构地区：[1]西北工业大学计算机学院,陕西西安710072 [2]西北工业大学软件学院,陕西西安710072 [3]西安电子科技大学生命科学技术学院,陕西西安710071

出　　处：《西北工业大学学报》2024年第5期969-978,共10页Journal of Northwestern Polytechnical University

基　　金：陕西省自然科学基础研究计划(2023-JC-YB-546,2024JC-YBMS-471)资助。

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

关 键 词：全同态加密 近似计算 自举 余数系统 插值拟合 拉格朗日插值 

分 类 号：TN918.1[电子电信—通信与信息系统]