同态密文处理方法、装置、电子设备及存储介质

1.本公开涉及计算机技术领域，尤其涉及一种同态密文处理方法、装置、电子设备及存储介质。


背景技术：

2.在密码学中，同态加密是一种特殊的加密方式，其允许在不进行解密的前提下对密文数据进行计算，所得到的计算结果等价于对相应明文数据先进行计算再进行同态加密的结果。基于同态加密技术，终端可以在不泄露用户隐私数据的前提下，将用户隐私数据进行加密再发送给云端服务器进行密文处理。由于同态加密的这种特性，其在金融服务、大数据医疗等隐私计算领域有丰富的应用场景。
3.阶梯函数即分段常值函数，是密码学中得一类基础函数，利用阶梯函数执行密文数据的同态计算是各种应用场景中的关键技术问题。对于支持近似计算的同态加密，阶梯函数的同态计算问题可以通过多项式逼近的方式解决，然而现有技术中利用阶梯函数的多项式逼近执行同态计算的计算效率和计算精度较低。


技术实现要素：

4.有鉴于此，本公开提出了一种同态密文处理方法、装置、电子设备及存储介质，能够提高对加密后的用户数据执行同态计算的计算效率和计算精度。
5.根据本公开的一方面，提供了一种同态密文处理方法，所述方法应用于服务器，包括：获取终端发送的待处理的同态密文以及针对所述同态密文的处理指令，所述同态密文包括终端对用户数据的加密结果，所述处理指令用于指示处理所述同态密文所需的阶梯函数，所述阶梯函数的取值区间包括多个不同的初始子区间，所述阶梯函数在同一初始子区间的函数值相同；确定与所述处理指令指示的阶梯函数逼近的复合多项式函数，所述复合多项式函数包括多个第一逼近多项式与第二逼近多项式，所述多个第一逼近多项式用于将所述阶梯函数对应的各个初始子区间迭代映射到各个初始子区间中点附近的目标子区间，各个目标子区间的区间范围小于各个初始子区间的区间范围，所述第二逼近多项式用于将各个目标子区间映射到所述阶梯函数在各个初始子区间对应的函数值；利用所述复合多项式函数执行对所述同态密文的同态计算，得到密文处理结果，并将所述密文处理结果发送给所述终端。
6.在一种可能的实现方式中，所述阶梯函数的取值区间包括n个初始子区间，所述复合多项式函数中包括k个第一逼近多项式，n和k为正整数，其中，所述确定与所述处理指令指示的阶梯函数逼近的复合多项式函数，包括：针对所述k个第一逼近多项式中的第k个第一逼近多项式，根据针对所述第k个第一逼近多项式所设置的多项式次数，构建待确定系数值的第k个第一初始多项式，1≤k≤k；基于所述阶梯函数对应的n个初始子区间，确定所述第k个第一初始多项式对应的n个待映射区间，并从所述第k个第一初始多项式对应的n个待映射区间中分别选取多个参考点，得到第一参考点集合；根据所述第一参考点集合、预设的
第一多项式系数阈值以及所述阶梯函数对应的标准化阶梯函数，确定所述第k个第一初始多项式中系数的系数值，其中，所述第k个第一初始多项式中系数的最大系数值小于或等于所述第一多项式系数阈值，所述标准化阶梯函数的取值区间与所述阶梯函数相同，且所述标准化阶梯函数在第1个子区间的函数值为所述取值区间的左边界点、在第n个子区间的函数值为所述取值区间的右边界点以及在第i个子区间的函数值为第i个子区间的中点，1＜i＜n；将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式。
7.在一种可能的实现方式中，所述基于所述阶梯函数对应的n个初始子区间，确定所述第k个第一初始多项式对应的n个待映射区间，包括：当k＝1时，根据所述n个初始子区间以及预设的输入精度，确定第1个第一初始多项式对应的n个待映射区间，所述输入精度表征所述复合多项式函数所具有的输入精度；当k≥k＞1时，将第k-1个第一初始多项式对应的n个待映射区间输入至第k-1个第一逼近多项式，得到所述第k-1个第一逼近多项式输出的n个映射后区间，并根据所述n个初始子区间各自的中点以及所述n个映射后区间的区间半径，确定所述第k个第一初始多项式对应的n个待映射区间。
8.在一种可能的实现方式中，所述根据所述第一参考点集合、预设的第一多项式系数阈值以及所述阶梯函数对应的标准化阶梯函数，确定所述第k个第一初始多项式中系数的系数值，包括：构建所述第k个第一初始多项式与所述标准化阶梯函数之间的第一线性规划方程组，所述第一线性规划方程组用于约束所述第k个第一初始多项式与所述标准化阶梯函数之间偏差的绝对值小于或等于第一压缩率参数与各个待映射区间的区间半径之间的乘积，以及约束所述第k个第一初始多项式中的最大系数小于或等于所述第一多项式系数阈值；以最小化所述第一压缩率参数为目标，将所述第一参考点集合中的各个参考点代入所述第一线性规划方程组，并求解代入各个参考点后的第一线性规划方程组，得到所述第k个第一初始多项式中系数的系数值以及所述第一压缩率参数的第一压缩率参数值。
9.在一种可能的实现方式中，所述将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式，包括：检测所述n个待映射区间中是否存在满足第一指定条件的极值点和边界点，所述第一指定条件包括：使已确定系数值的第k个第一初始多项式与所述标准化阶梯函数之间偏差的绝对值大于所述第一压缩率参数值与待映射区间的区间半径之间的乘积；在所述n个待映射区间中不存在满足所述第一指定条件的极值点和边界点的情况下，将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式；或，在所述n个待映射区间中存在满足所述第一指定条件的极值点和边界点的情况下，将满足所述第一指定条件的极值点和边界值添加到所述第一参考点集合中，得到第二参考点集合；根据所述第二参考点集合、所述第一多项式系数阈值以及所述标准化阶梯函数，重新确定所述第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式。
10.在一种可能的实现方式中，所述根据第二参考点集合、所述第一多项式系数阈值以及所述标准化阶梯函数，重新确定所述第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式，包括：根据所述第二参考点集合、已确定系数值的第k个第一初始多项式、所述标准化阶梯函数以及所述第k个第一初始多项式对应的各个待映射区间的区间半径，确定各个待映射区间各自对应的实际区间压缩率中的最大压缩率；在所述第一压缩率参数值的加权值大于所述最大压缩率的
情况下，根据所述第二参考点集合、所述第一多项式系数阈值以及所述标准化阶梯函数，重新确定所述第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式；或，在所述第一压缩率参数值的加权值小于或等于所述最大压缩率的情况下，将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式。
11.在一种可能的实现方式中，所述确定与所述处理指令指示的阶梯函数逼近的复合多项式函数，包括：根据针对所述第二逼近多项式所设置的多项式次数，构建待确定系数值的第二初始多项式；根据所述n个子区间各自的中点以及所述k个第一逼近多项式中的第k个第一逼近多项式输出的n个映射后区间的区间半径，确定所述第二初始多项式对应的n个待映射区间，并从所述第二初始多项式对应的n个待映射区间中选取多个参考点，得到第三参考点集合；根据所述第三参考点集合、预设的第二多项式系数阈值以及所述阶梯函数，确定所述第二初始多项式中系数的系数值，所述第二初始多项式中系数的最大系数值小于或等于所述第二多项式阈值；将已确定系数值的第二初始多项式作为第二逼近多项式。
12.在一种可能的实现方式中，所述根据所述第三参考点集合、预设的第二多项式系数阈值以及所述阶梯函数，确定所述第二初始多项式中系数的系数值，包括：构建所述第二初始多项式与所述阶梯函数之间的第二线性规划方程组，所述第二线性规划方程组用于约束所述第二初始多项式与所述阶梯函数之间偏差的绝对值小于或等于第二压缩率参数与所述第二初始多项式对应的各个待映射区间的区间半径之间的乘积，以及约束所述第二初始多项式中的最大系数小于或等于所述第二多项式系数阈值；以最小化所述第二压缩率参数为目标，将所述第三参考点集合中的各个参考点代入所述第二线性规划方程组，并求解代入各个参考点后的第二线性规划方程组，得到所述第二初始多项式中系数的系数值以及所述第二压缩率参数的第二压缩率参数值。
13.在一种可能的实现方式中，所述将已确定系数值的第二初始多项式作为第二逼近多项式，包括：检测所述第二初始多项式对应的n个待映射区间中是否存在满足第二指定条件的极值点和边界点，所述第二指定条件包括：使已确定系数值的第二初始多项式与所述阶梯函数之间偏差的绝对值大于所述第二压缩率参数值与第二初始多项式对应的待映射区间的区间半径之间的乘积；在所述第二初始多项式对应的n个待映射区间中不存在满足所述第二指定条件的极值点和边界点的情况下，将已确定系数值的第二初始多项式作为第二逼近多项式；或，在所述第二初始多项式对应的n个待映射区间中存在满足所述第二指定条件的极值点和边界点的情况下，将满足所述第二指定条件的极值点和边界值添加到所述第三参考点集合中，得到第四参考点集合；根据所述第四参考点集合、所述第二多项式系数阈值以及所述阶梯函数，重新确定所述第二初始多项式中系数的系数值，并将已重新确定系数值的第二初始多项式作为所述第二逼近多项式。
14.在一种可能的实现方式中，所述方法还包括：根据所述第二逼近多项式与所述阶梯函数的函数值之间偏差的最大值，以及预设的误差界，确定所述复合多项式函数的输出精度，所述误差界用于控制所述复合多项式函数的同态计算精度。
15.根据本公开的另一方面，提供了一种同态密文处理装置，所述装置应用于服务器，包括：获取模块，用于获取终端发送的待处理的同态密文以及针对所述同态密文的处理指令，所述同态密文包括终端对用户数据的加密结果，所述处理指令用于指示处理所述同态
密文所需的阶梯函数，所述阶梯函数的取值区间包括多个不同的初始子区间，所述阶梯函数在同一初始子区间的函数值相同；确定模块，用于确定与所述处理指令指示的阶梯函数逼近的复合多项式函数，所述复合多项式函数包括多个第一逼近多项式与第二逼近多项式，所述多个第一逼近多项式用于将所述阶梯函数对应的各个初始子区间迭代映射到各个初始子区间中点附近的目标子区间，各个目标子区间的区间范围小于各个初始子区间的区间范围，所述第二逼近多项式用于将各个目标子区间映射到所述阶梯函数在各个初始子区间对应的函数值；执行模块，用于利用所述复合多项式函数执行对所述同态密文的同态计算，得到密文处理结果，并将所述密文处理结果发送给所述终端。
16.在一种可能的实现方式中，所述阶梯函数的取值区间包括n个初始子区间，所述复合多项式函数中包括k个第一逼近多项式，n和k为正整数，其中，所述确定与所述处理指令指示的阶梯函数逼近的复合多项式函数，包括：针对所述k个第一逼近多项式中的第k个第一逼近多项式，根据针对所述第k个第一逼近多项式所设置的多项式次数，构建待确定系数值的第k个第一初始多项式，1≤k≤k；基于所述阶梯函数对应的n个初始子区间，确定所述第k个第一初始多项式对应的n个待映射区间，并从所述第k个第一初始多项式对应的n个待映射区间中分别选取多个参考点，得到第一参考点集合；根据所述第一参考点集合、预设的第一多项式系数阈值以及所述阶梯函数对应的标准化阶梯函数，确定所述第k个第一初始多项式中系数的系数值，其中，所述第k个第一初始多项式中系数的最大系数值小于或等于所述第一多项式系数阈值，所述标准化阶梯函数的取值区间与所述阶梯函数相同，且所述标准化阶梯函数在第1个子区间的函数值为所述取值区间的左边界点、在第n个子区间的函数值为所述取值区间的右边界点以及在第i个子区间的函数值为第i个子区间的中点，1＜i＜n；将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式。
17.在一种可能的实现方式中，所述基于所述阶梯函数对应的n个初始子区间，确定所述第k个第一初始多项式对应的n个待映射区间，包括：当k＝1时，根据所述n个初始子区间以及预设的输入精度，确定第1个第一初始多项式对应的n个待映射区间，所述输入精度表征所述复合多项式函数所具有的输入精度；当k≥k＞1时，将第k-1个第一初始多项式对应的n个待映射区间输入至第k-1个第一逼近多项式，得到所述第k-1个第一逼近多项式输出的n个映射后区间，并根据所述n个初始子区间各自的中点以及所述n个映射后区间的区间半径，确定所述第k个第一初始多项式对应的n个待映射区间。
18.在一种可能的实现方式中，所述根据所述第一参考点集合、预设的第一多项式系数阈值以及所述阶梯函数对应的标准化阶梯函数，确定所述第k个第一初始多项式中系数的系数值，包括：构建所述第k个第一初始多项式与所述标准化阶梯函数之间的第一线性规划方程组，所述第一线性规划方程组用于约束所述第k个第一初始多项式与所述标准化阶梯函数之间偏差的绝对值小于或等于第一压缩率参数与各个待映射区间的区间半径之间的乘积，以及约束所述第k个第一初始多项式中的最大系数小于或等于所述第一多项式系数阈值；以最小化所述第一压缩率参数为目标，将所述第一参考点集合中的各个参考点代入所述第一线性规划方程组，并求解代入各个参考点后的第一线性规划方程组，得到所述第k个第一初始多项式中系数的系数值以及所述第一压缩率参数的第一压缩率参数值。
19.在一种可能的实现方式中，所述将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式，包括：检测所述n个待映射区间中是否存在满足第一指定条件的极值点
和边界点，所述第一指定条件包括：使已确定系数值的第k个第一初始多项式与所述标准化阶梯函数之间偏差的绝对值大于所述第一压缩率参数值与待映射区间的区间半径之间的乘积；在所述n个待映射区间中不存在满足所述第一指定条件的极值点和边界点的情况下，将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式；或，在所述n个待映射区间中存在满足所述第一指定条件的极值点和边界点的情况下，将满足所述第一指定条件的极值点和边界值添加到所述第一参考点集合中，得到第二参考点集合；根据所述第二参考点集合、所述第一多项式系数阈值以及所述标准化阶梯函数，重新确定所述第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式。
20.在一种可能的实现方式中，所述根据第二参考点集合、所述第一多项式系数阈值以及所述标准化阶梯函数，重新确定所述第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式，包括：根据所述第二参考点集合、已确定系数值的第k个第一初始多项式、所述标准化阶梯函数以及所述第k个第一初始多项式对应的各个待映射区间的区间半径，确定各个待映射区间各自对应的实际区间压缩率中的最大压缩率；在所述第一压缩率参数值的加权值大于所述最大压缩率的情况下，根据所述第二参考点集合、所述第一多项式系数阈值以及所述标准化阶梯函数，重新确定所述第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式；或，在所述第一压缩率参数值的加权值小于或等于所述最大压缩率的情况下，将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式。
21.在一种可能的实现方式中，所述确定与所述处理指令指示的阶梯函数逼近的复合多项式函数，包括：根据针对所述第二逼近多项式所设置的多项式次数，构建待确定系数值的第二初始多项式；根据所述n个子区间各自的中点以及所述k个第一逼近多项式中的第k个第一逼近多项式输出的n个映射后区间的区间半径，确定所述第二初始多项式对应的n个待映射区间，并从所述第二初始多项式对应的n个待映射区间中选取多个参考点，得到第三参考点集合；根据所述第三参考点集合、预设的第二多项式系数阈值以及所述阶梯函数，确定所述第二初始多项式中系数的系数值，所述第二初始多项式中系数的最大系数值小于或等于所述第二多项式阈值；将已确定系数值的第二初始多项式作为第二逼近多项式。
22.在一种可能的实现方式中，所述根据所述第三参考点集合、预设的第二多项式系数阈值以及所述阶梯函数，确定所述第二初始多项式中系数的系数值，包括：构建所述第二初始多项式与所述阶梯函数之间的第二线性规划方程组，所述第二线性规划方程组用于约束所述第二初始多项式与所述阶梯函数之间偏差的绝对值小于或等于第二压缩率参数与所述第二初始多项式对应的各个待映射区间的区间半径之间的乘积，以及约束所述第二初始多项式中的最大系数小于或等于所述第二多项式系数阈值；以最小化所述第二压缩率参数为目标，将所述第三参考点集合中的各个参考点代入所述第二线性规划方程组，并求解代入各个参考点后的第二线性规划方程组，得到所述第二初始多项式中系数的系数值以及所述第二压缩率参数的第二压缩率参数值。
23.在一种可能的实现方式中，所述将已确定系数值的第二初始多项式作为第二逼近多项式，包括：检测所述第二初始多项式对应的n个待映射区间中是否存在满足第二指定条
件的极值点和边界点，所述第二指定条件包括：使已确定系数值的第二初始多项式与所述阶梯函数之间偏差的绝对值大于所述第二压缩率参数值与第二初始多项式对应的待映射区间的区间半径之间的乘积；在所述第二初始多项式对应的n个待映射区间中不存在满足所述第二指定条件的极值点和边界点的情况下，将已确定系数值的第二初始多项式作为第二逼近多项式；或，在所述第二初始多项式对应的n个待映射区间中存在满足所述第二指定条件的极值点和边界点的情况下，将满足所述第二指定条件的极值点和边界值添加到所述第三参考点集合中，得到第四参考点集合；根据所述第四参考点集合、所述第二多项式系数阈值以及所述阶梯函数，重新确定所述第二初始多项式中系数的系数值，并将已重新确定系数值的第二初始多项式作为所述第二逼近多项式。
24.在一种可能的实现方式中，所述装置还包括：输出精度确定模块，用于根据所述第二逼近多项式与所述阶梯函数的函数值之间偏差的最大值，以及预设的误差界，确定所述复合多项式函数的输出精度，所述误差界用于控制所述复合多项式函数的同态计算精度。
25.根据本公开的另一方面，提供了一种电子设备，包括：处理器；用于存储处理器可执行指令的存储器；其中，所述处理器被配置为在执行所述存储器存储的指令时，实现上述方法。
26.根据本公开的另一方面，提供了一种非易失性计算机可读存储介质，其上存储有计算机程序指令，其中，所述计算机程序指令被处理器执行时实现上述方法。
27.根据本公开的另一方面，提供了一种计算机程序产品，包括计算机可读代码，或者承载有计算机可读代码的非易失性计算机可读存储介质，当所述计算机可读代码在电子设备的处理器中运行时，所述电子设备中的处理器执行上述方法。
28.根据本公开的实施例，利用与处理同态密文所需的阶梯函数逼近的复合多项式函数，也即利用由多个第一逼近多项式和第二逼近多项式构成的复合多项式函数执行对同态密文的同态计算，能够提高对同态密文的同态计算效率和计算精度，满足各种应用场景的同态计算需求。
29.根据下面参考附图对示例性实施例的详细说明，本公开的其它特征及方面将变得清楚。
附图说明
30.包含在说明书中并且构成说明书的一部分的附图与说明书一起示出了本公开的示例性实施例、特征和方面，并且用于解释本公开的原理。
31.图1示出根据本公开一实施例的一种应用场景的示意图。
32.图2示出根据本公开一实施例的同态密文处理方法的流程图。
33.图3示出根据本公开一实施例的一种多项式逼近方式的流程图。
34.图4示出根据本公开一实施例的一种多项式逼近方式的流程图。
35.图5示出根据本公开一实施例的同态密文处理装置的框图。
36.图6示出根据本公开一实施例的一种电子设备1900的框图。
具体实施方式
37.以下将参考附图详细说明本公开的各种示例性实施例、特征和方面。附图中相同
的附图标记表示功能相同或相似的元件。尽管在附图中示出了实施例的各种方面，但是除非特别指出，不必按比例绘制附图。
38.在这里专用的词“示例性”意为“用作例子、实施例或说明性”。这里作为“示例性”所说明的任何实施例不必解释为优于或好于其它实施例。
39.另外，为了更好的说明本公开，在下文的具体实施方式中给出了众多的具体细节。本领域技术人员应当理解，没有某些具体细节，本公开同样可以实施。在一些实例中，对于本领域技术人员熟知的方法、手段、元件和电路未作详细描述，以便于凸显本公开的主旨。
40.如上所述，基于同态加密技术，终端可以在不泄露用户隐私数据的前提下，将用户隐私数据进行加密再发送给云端服务器进行密文处理。由于同态加密的这种特性，其在金融服务、大数据医疗等隐私计算领域有丰富的应用场景。利用阶梯函数执行密文数据的同态计算是各种应用场景中的关键技术问题。阶梯函数即分段常值函数，是密码学中得一类基础函数，并且与机器学习中的模函数、relu函数等具有重要关联。其中，阶梯函数例如可以包括符号函数、取整函数、分段光滑函数、分桶函数等。
41.具体地，假设κ(x)是定义在区间[a,b]上的实函数，其中，区间[a,b]分段划分为a＝a0《a1《
…
《ai＝b，若存在实数yi(1≤i≤i)，使得
[0042]
κ(x)＝yi,x∈(a
i-1
,ai),1≤i≤i
[0043]
则可以称函数κ(x)称为阶梯函数。
[0044]
特别地，如果i＝1时，y1＝a，i＝i时，yi＝b且1＜i＜i时，则称这样的κ(x)是标准化阶梯函数(也可称为正规化阶梯函数)。如果是标准化阶梯函数，且具有和κ(x)相同的区间划分a＝a0《a1《
…
《ai＝b，则称是κ(x)的标准化阶梯函数。
[0045]
可知晓，对于支持近似计算的同态加密，阶梯函数的同态计算问题可以通过多项式逼近的方式解决，即首先给出阶梯函数的一个多项式逼近，再利用此多项式逼近对密文数据进行同态计算，从而得到阶梯函数的同态计算的一个近似结果。其中，通过控制多项式逼近的精度和同态加密的计算精度，可以实现较高精度的阶梯函数同态计算。因此，对于阶梯函数的同态计算问题，其关键在于如何得到其一个多项式逼近，能够在满足计算精度要求的前提下同时具有较高的同态计算效率。而现有方式所得到的多项式逼近的同态计算效率和计算精度较低，无法满足各种应用场景的同态计算需求。
[0046]
有鉴于此，本公开实施例提供的一种同态密文处理方法，利用与处理同态密文所需的阶梯函数逼近的复合多项式函数，也即利用由多个第一逼近多项式和第二逼近多项式构成的复合多项式函数执行对同态密文的同态计算，能够提高对同态密文的同态计算效率和计算精度，满足各种应用场景的同态计算需求。
[0047]
图1示出本公开一实施例的一种应用场景的示意图，如图1所示，当终端需要服务器协助处理用户数据(例如金融场景下，需要用户的资产数据进行统计排序；医疗场景下，需要对用户的病例数据进行筛选分析等)，又需要确保用户数据安全时，终端可以对用户数据进行加密得到同态密文，并将同态密文和针对该同态密文的处理指令发送给服务器，由服务器基于处理指令执行对同态密文的同态计算，并将同态计算结果返回给终端；其中，处理指令可以是终端基于自身业务逻辑对同态密文的计算需求向服务器发送的指令，该处理指令可以指示服务器采用何种阶梯函数处理该同态密文，在该场景下，由于同态加密的特
性，服务器无法直接利用阶梯函数处理同态密文，因此可以通过计算阶梯函数的多项式逼近来处理同态密文，但是现有多项式逼近方式所得到的多项式逼近函数执行同态计算的计算效率和计算精度较低，因此服务器可以采用本公开实施例的同态加密方法来提高同态计算的计算效率和计算精度，也即，本公开实施例所要解决的技术问题以及产生的技术效果是与具体应用场景紧密结合的，可以解决各种同态加密场景中对同态密文的同态计算效率低和同态计算精度低的问题，能够提高同态加密场景中对同态密文进行同态计算的计算效率和计算精度。
[0048]
本公开实施例的同态密文处理方法可以部署于服务器上，该服务器可以位于云端或本地，可以是实体设备，也可以是虚拟设备，如虚拟机、容器等，具有无线通信功能，其中，无线通信功能可设置于该服务器的芯片(系统)或其他部件或组件。可以是指具有无线连接功能的设备，无线连接的功能是指可以通过wi-fi、蓝牙等无线连接方式与其他服务器或终端设备进行连接，本公开实施例涉及的服务器也可以具有有线连接进行通信的功能。例如，本公开实施例涉及的服务器可位于云端，与终端设备进行通信，接收终端设备发送的同态密文以及针对同态密文的处理指令，利用部署于服务器的同态密文处理方法基于处理指令完成对同态密文的同态计算并将同态计算结果返回给终端设备。
[0049]
当然，本公开实施例的同态密文处理方法也可以通过软件或硬件改造部署在各种终端设备上，本公开实施例涉及的终端设备可以是指具有无线连接功能的设备，无线连接的功能是指可以通过wifi、蓝牙等无线连接方式与其他终端设备进行连接，本公开实施例涉及的终端设备也可以具有有线连接进行通信的功能。本公开实施例涉及的终端设备可以是触屏的、也可以是非触屏的、也可以是没有屏幕的，触屏的可以通过手指、触控笔等在显示屏幕上点击、滑动等方式对终端设备进行控制，非触屏的设备可以连接鼠标、键盘、触控面板等输入设备，通过输入设备对终端设备进行控制，没有屏幕的设备比如说可以是没有屏幕的蓝牙音箱等。举例来说，本技术的终端设备可以是智能手机、上网本、平板电脑、笔记本电脑、可穿戴电子设备(如智能手环、智能手表等)、tv、虚拟现实设备、音响、电子墨水，等等。
[0050]
以下通过图2至图4，对本公开实施例提供的同态密文处理方法进行详细介绍。
[0051]
图2示出根据本公开一实施例的同态密文处理方法的流程图。该方法可以由上述服务器或其它终端设备执行。如图2所示，该同态密文处理方法包括：
[0052]
步骤s21，获取终端发送的待处理的同态密文以及针对同态密文的处理指令，同态密文包括终端对用户数据的加密结果，处理指令用于指示处理同态密文所需的阶梯函数，阶梯函数的取值区间包括多个不同的初始子区间，阶梯函数在同一初始子区间的函数值相同。
[0053]
可理解，不同应用场景中的用户数据不同，例如，在金融场景里，用户数据可以包括用户的资产数据，个人隐私数据等；医疗场景里，用户数据可以包括患者的病例数据、个人隐私数据等，本公开实施例对于用户数据的具体类型不作限制。
[0054]
如上所述，当终端需要服务器利用阶梯函数协助处理用户数据，例如金融场景中，需要对用户的资产数据进行统计排序；医疗场景中，需要对用户的病例数据进行筛选分析等，同时又需要确保用户数据的安全时，终端可以对用户数据进行加密得到同态密文，并将该同态密文以及对应的处理指令发送至服务器；其中，终端可以采用本领域已知的数据加
密方式对用户数据进行加密，对此本公开实施例不作限制。
[0055]
应理解，不用应用场景中具有不同业务逻辑需求，不同业务需求对用户数据的处理需求不同，也即处理同态密文所需的阶梯函数不同，因此，终端可以基于自身业务逻辑对同态密文的处理需求向服务器发送对应的处理指令，该处理指令可以指示服务器采用何种阶梯函数处理该同态密文。
[0056]
其中，阶梯函数的取值区间例如可以表示为[a,b]，也即代表阶梯函数的最大取值范围；取值区间包括多个初始子区间，也即取值区间[a,b]可以分段a＝a0《a1《
…
《ai＝b，也即可以划分为多个初始子区间[a0,a1]、
…
、[a
i-1
,ai]、
…
、[a
i-1
,ai]。如上所述，阶梯函数可以表示为κ(x)＝yi,x∈(a
i-1
,ai),1≤i≤i，这代表阶梯函数κ(x)在同一初始子区间(a
i-1
,ai)的函数值yi相同。应理解，本公开实施例对于取值区间的范围、以及取值区间内初始子区间的数量不作限制。
[0057]
步骤s22，确定与处理指令指示的阶梯函数逼近的复合多项式函数，复合多项式函数包括多个第一逼近多项式与第二逼近多项式，多个第一逼近多项式用于将阶梯函数对应的各个初始子区间迭代映射到各个初始子区间中点附近的目标子区间，各个目标子区间的区间范围小于各个初始子区间的区间范围，第二逼近多项式用于将各个目标子区间映射到阶梯函数在各个初始子区间对应的函数值。
[0058]
其中，假设复合多项式函数表示为该复合多项式构成阶梯函数κ(x)的逼近，其中，f1,
…
,fk代表k个第一逼近多项式，该k个第一逼近多项式可以将阶梯函数的各个初始子区间(a
i-1
,ai)迭代地映射到各个初始子区间中点附近的目标子区间，即将初始子区间的区间值映射到κ(x)的标准化阶梯函数的逼近；g代表第二逼近多项式，该第二逼近多项式可以将目标子区间(包括初始子区间的中点)映射到阶梯函数κ(x)的函数值，即将映射到κ(x)的逼近。
[0059]
应理解，本领域技术人员可以根据实际需求设置复合多项式函数中包含的第一逼近多项式的数量k，对此本公开实施例不作限制。其中，多个第一逼近多项式f1,
…
,fk将阶梯函数的初始子区间(a
i-1
,ai)迭代地映射到初始子区间中点附近的目标子区间，可以表示为：
[0060][0061]
其中，ε代表复合多项式函数的输入精度，可根据实际需求自定义设置，例如可设置为2-7
、2-10
、2-20
等，zi代表初始子区间的中点，t
ik
可以代表第k个第一逼近多项式最终输出的目标子区间的区间半径，t
i1
、t
i2
…
、t
i(k-1)
可以代表前k-1个第一逼近多项式迭代输出的映射后区间的区间半径。
[0062]
其中，第二逼近多项式g将目标子区间[z
i-t
ik
,zi+t
ik
]映射到阶梯函数的函数值yi，可以表示为：其中，2-α
代表复合多项式函数的输出精度，该输出精度可以与上述输入精度ε相同，也可以不同。应理解，该输出精度与上述输入精度可以表征复合多项式函数与阶梯函数之间的误差，该输出精度与输入精度越小可代表复合多项式函数与阶梯函数之间的误差越小，也即复合多项式函数与阶梯函数的逼近
程度越高，利用复合多项式执行同态计算的计算精度就越高，同时由上述多个第一逼近多项式以及第二逼近多项式构成的复合多项式函数在对同态密文执行同态计算时的计算效率更高。
[0063]
在实际应用中，服务器可以预先确定出各种已知阶梯函数逼近的复合多项式函数，构成函数库，这样可以在接收到终端发送的处理指令后，可以直接从该函数库中调用处理指令指示的阶梯函数所对应的复合多项式函数；或者，处理指令还可以指示自定义的阶梯函数的取值范围、函数结构、系数参数等函数信息，服务器可以根据处理指令指示的该些函数信息所自定义的阶梯函数，即时确定出该自定义的阶梯函数所对应的复合多项式函数，对此本公开实施例不作限制。
[0064]
步骤s23，利用复合多项式函数执行对同态密文的同态计算，得到密文处理结果，并将密文处理结果发送给终端。
[0065]
其中，基于上述复合多项式函数表示为同态密文可以相当于x，利用复合多项式函数执行对同态密文的同态计算，得到密文处理结果，例如可以包括：将同态密文x输入至第1个第一逼近多项式f1中，得到f1的输出结果f1(x)，再将f1的输出结果f1(x)输入至第2个第一逼近多项式f2中，得到f2的输出结果f2(x)，依次类推，将第k-1个第一逼近多项式f
k-1
的输出结果f
k-1
(x)输入至第k个第一逼近多项式fk，得到fk的输出结果fk(x)，然后将该fk的输出结果fk(x)输入至第二逼近多项式g中，得到该g的输出结果g(x)，该第二逼近多项式g的输出结果g(x)也即同态密文的处理结果。
[0066]
应理解，利用复合多项式函数执行对同态密文的同态计算的计算结果，与利用阶梯函数对用户数据进行计算所得到的明文计算结果再进行加密后的加密结果等价。
[0067]
根据本公开实施例，利用与处理同态密文所需的阶梯函数逼近的复合多项式函数，也即利用由多个第一逼近多项式和第二逼近多项式构成的复合多项式函数执行对同态密文的同态计算，能够提高对同态密文的同态计算效率和计算精度，满足各种应用场景的同态计算需求。
[0068]
可知晓，对于阶梯函数的多项式逼近方式，目前有两种相关技术，其中一种技术是分段光滑函数的逼近技术，这种技术能够对任意分段光滑但存在奇异点的函数给出任意程度逼近的多项式，但是，这种技术给出的多项式次数很高，导致其同态计算的效率较低，同时，由于阶梯函数存在间断点，现有的分段光滑函数的逼近算法也无法适用于阶梯函数的逼近问题。另外一种技术是符号函数的多项式逼近技术，符号函数是一种仅有一个间断点的特殊阶梯函数，其多项式逼近方式已有许多成熟解决方法，但由于阶梯函数一般具有多个间断点，这些方式均无法直接用于解决一般的阶梯函数的多项式逼近。因此，现有的技术尚无法处理一般阶梯函数的多项式逼近。
[0069]
有鉴于此，本公开实施例还提供一种阶梯函数的多项式逼近方法，采用逼近问题中常用的复合多项式思想，构造一列多项式，使得其复合多项式恰为阶梯函数的逼近函数。本公开实施例提供的多项式逼近方法，能够对于任意的阶梯函数确定出其符合多项式逼近的具体构造，也即能够确定出任意阶梯函数的复合多项式逼近。本公开实施例提供的多项式逼近方法能够保证复合多项式的构造在逼近效率上达到最优，也即用复合多项式进行同态计算时的计算效率最优，并且还可以灵活的控制所构造的复合多项式的系数上界，使其能够适用于不同精度的同态计算任务。
[0070]
假设阶梯函数的取值区间包括n个初始子区间，复合多项式函数中包括k个第一逼近多项式，n和k为正整数，图3示出根据本公开一实施例的一种多项式逼近方式的流程图，图3示出的多项式逼近方式可以用于确定任意阶梯函数对应的复合多项式函数中的多个第一逼近多项式，如图3所示，上述步骤s22确定与处理指令指示的阶梯函数逼近的复合多项式函数，可以包括：
[0071]
步骤s221，针对k个第一逼近多项式中的第k个第一逼近多项式，根据针对第k个第一逼近多项式设置的多项式次数，构建待确定系数值的第k个第一初始多项式，1≤k≤k。
[0072]
在实际应用中，用户可以根据实际需求设置各个第一逼近多项式各自具有的多项式次数，应理解，不同第一逼近多项式的多项式次数可以相同也可以不同；在已知用户设置的多项式次数后，可以从预设的基多项式集合中选取至少一种基多项式，构建与多项式次数匹配的第一初始多项式。其中，基多项式可以理解为构成初始多项式的基础项。
[0073]
应理解，本领域技术人员可以根据实际需求设计基多项式集合中包含的基多项式的数量和种类，例如，基多项式集合至少包括但不限于“d+ex”、“hx
2”、“mx
3”等基多项式，其中，d、e、h、m代表待确定系数值的系数，本公开实施例对于基多项式集合中基多项式的数量和类型不作限制。示例性地，假设针对第1个第一逼近多项式设置的多项式次数为2，则可以从上述基多项式集合中选取“d+ex”和“hx
2”，构建d+ex+hx2作为第1个第一初始多项式。
[0074]
步骤s222，基于阶梯函数对应的n个初始子区间，确定第k个第一初始多项式对应的n个待映射区间，并从第k个第一初始多项式对应的n个待映射区间中分别选取多个参考点，得到第一参考点集合。
[0075]
在一种可能的实现方式中，基于阶梯函数对应的n个初始子区间，确定第k个第一初始多项式对应的n个待映射区间，包括：
[0076]
当k＝1时，根据n个初始子区间以及预设的输入精度，确定第1个第一初始多项式对应的n个待映射区间，输入精度表征复合多项式函数所具有的输入精度；
[0077]
当k≥k＞1时，将第k-1个第一初始多项式对应的n个待映射区间输入至第k-1个第一逼近多项式，得到第k-1个第一逼近多项式输出的n个映射后区间，并根据n个初始子区间各自的中点以及n个映射后区间的区间半径，确定第k个第一初始多项式对应的n个待映射区间。
[0078]
示例性地，假设n为3，也即阶梯函数对应有3个初始子区间，分为表示为[a0,a1]、[a1,a2]、[a2,a3]，输入精度表示为ε，则第1个第一初始多项式对应的n个待映射区间可以表示为[a0+ε,a
1-ε]、[a1+ε,a
2-ε]、[a2+ε,a
3-ε]，也即可以将各个初始子区间的左端点加输入精度，将右端点减输入精度，得到第1个第一初始多项式对应的各个待映射区间；
[0079]
应理解，在构建出第1个初始多项式后，可以通过后续步骤s223至步骤s224得到第1个第一逼近多项式，进而对于第2个第一初始多项式，可以将第1个第一初始多项式对应的3个待映射区间[a0,a1]、[a1,a2]、[a2,a3]分别输入至第1个第一逼近多项式，得到第1个第一逼近多项式输出的3个映射后区间，假设该3个映射后区间分别表示为假设该3个映射后区间分别表示为基于该3个映射后区间可以计算出该3个映射后区间的区间半径；
[0080]
其中，第1个第一逼近多项式输出的第1个映射后区间的区间半径为第1个第一逼近多项式输出的第2个映射后区间的区间半径为第1个第一逼
近多项式输出的第3个映射后区间的区间半径为然后可以根据该3个映射后区间的区间半径，以及上述3个初始子区间各自的中点，也即，第1个初始子区间的中点第2个初始子区间的中点第3个初始子区间的中点确定第2个第一初始多项式对应的3个待映射区间，也即确定待输入至第2个第一初始多项式的3个待映射区间；
[0081]
其中，可以将3个初始子区间的中点分别与对应的映射后区间的区间半径相加，得到第2个第一初始多项式的3个待映射区间的右端点，以及将3个初始子区间的中点分别与对应的映射后区间的区间半径相减，得到第2个第一初始多项式的3个待映射区间的左端点，例如第2个第一初始多项式对应的3个待映射区间可以分别表示为[z
1-t
12
,z1+t
12
]、[z
2-t
22
,z2+t
22
]、[z
2-t
22
,z2+t
22
]。应理解，在得到第2个初始多项式对应的3个待映射区间后，可以通过执行后续步骤s223至步骤s224得到第2个第一逼近多项式，进而可以将第2个第一初始多项式对应的3个待映射区间输入至第2个第一逼近多项式，得到第2个第一逼近多项式输出的3个映射后区间，并根据3个初始子区间各自的中点以及第2个第一逼近多项式输出的3个映射后区间的区间半径，确定第3个第一初始多项式对应的3个待映射区间，以此类推，可以迭代确定出k≥k＞1中的第k个第一初始多项式对应的3个待映射区间。
[0082]
需要说明的是，以上是以3个初始子区间为例介绍上述第k个第一初始多项式对应的n个待映射区间的确定方式，实际上，阶梯函数对应的初始子区间的数量和范围可根据实际需求自定义设置，对此本公开实施例不限制。
[0083]
在实际应用中，例如可以采用随机选取、递增选取、均匀选取等本领域已知的选取方式，实现从第k个第一初始多项式对应的n个待映射区间中分别选取多个参考点，得到第一参考点集合，对此本公开实施例不作限制。应理解，本公开实施例对于参考点的选取方式和选取数量不作限制，也即对第一参考点集合中参考点的数量不作限制。
[0084]
步骤s223，根据第一参考点集合、预设的第一多项式系数阈值以及阶梯函数对应的标准化阶梯函数，确定第k个第一初始多项式中系数的系数值。
[0085]
其中，第k个第一初始多项式中系数的最大系数值小于或等于第一多项式系数阈值，标准化阶梯函数的取值区间与阶梯函数相同，也即，标准化阶梯函数的取值区间与阶梯函数相同，例如均为[a,b]，且标准化阶梯函数在第1个子区间[a0,a1]的函数值y1为取值区间[a,b]的左边界点a、在第n个子区间[a
n-1
,an]的函数值为取值区间[a,b]的右边界点b以及在第i个子区间[a
i-1
,ai]的函数值yi为第i个子区间的中点1＜i＜n。
[0086]
其中，用户根据实际需求设置第一多项式系数阈值的具体数值，对此本公开实施例不作限制。通过设置第一多项式系数阈值，可以灵活控制所生成的复合多项式的系数上界，使其能够适用于不同精度的同态计算任务。
[0087]
在一种可能的实现方式中，根据第一参考点集合、预设的第一多项式系数阈值以及阶梯函数对应的标准化阶梯函数，确定第k个第一初始多项式中系数的系数值，包括：
[0088]
构建第k个第一初始多项式与标准化阶梯函数之间的第一线性规划方程组，第一线性规划方程组用于约束第k个第一初始多项式与标准化阶梯函数之间偏差的绝对值小于或等于第一压缩率参数与各个待映射区间的区间半径之间的乘积，以及约束第k个第一初
始多项式中的最大系数小于或等于第一多项式系数阈值；
[0089]
以最小化第一压缩率参数为目标，将第一参考点集合中的各个参考点代入第一线性规划方程组，并求解代入各个参考点后的第一线性规划方程组，得到第k个第一初始多项式中系数的系数值以及第一压缩率参数的第一压缩率参数值。
[0090]
示例性地，上述第k个第一初始多项式fk与标准化阶梯函数之间的第一线性规划方程组可以表示为公式(1)：
[0091][0092]
其中，χ代表第一参考点集合，x
l
代表第一参考点集合中的任一参考点，代表阶梯函数的标准化阶梯函数，c代表第一压缩率参数，t
nk
代表第k第一初始多项式对应的n个待映射区间中的第n个待映射区间的区间半径，c
max
(fk)代表第k个第一初始多项式fk的系数中的最大系数，b代表第一多项式系数阈值。
[0093]
应理解，通过上述步骤s222可以确定出各个第一初始多项式对应的n个待映射区间，进而可以计算出各个待映射区间的区间半径；上述公式(1)中代表约束第k个第一初始多项式与标准化阶梯函数之间偏差的绝对值小于或等于第一压缩率参数与各个待映射区间的区间半径之间的乘积，上述c
max
(fk)≤b代表约束第k个第一初始多项式中的最大系数小于或等于第一多项式系数阈值。
[0094]
在实际应用中，例如可以采用本领域任意已知的线性规划求解器或整数规划求解器等求解器，实现以最小化第一压缩率参数为目标，求解代入各个参考点后的第一线性规划方程组，得到第k个第一初始多项式中系数的系数值以及第一压缩率参数的第一压缩率参数值，也即，本公开实施例对于上述第一线性规划方程组的求解方式不作限制，只要能求解出第k个第一初始多项式中系数的系数值以及第一压缩率参数的第一压缩率参数值即可。
[0095]
其中，第一压缩率参数值可以理解为当前计算出的最优区间压缩率，该第一压缩率参数值能够表征已确定系数值的第一初始多项式所输入的待映射区间与输出的映射后区间之间的比值。求解上述第一线性规划方程组，相当于使得第一压缩率参数c达到最优也即最小，或者说，尽可能地让fk把待映射区间值映射到初始子区间中点附近更小的子区间上，且多项式系数小于设置的系数上界。
[0096]
步骤s224，将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式。
[0097]
在实际应用中，在得到第k个第一初始多项式中各个系数的系数值后，可以将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式。
[0098]
考虑到，上述步骤s223是利用从n个待映射区间中选取多个参考点所构成的第一参考点集合来确定的第k个第一初始多项式中各个系数的系数值，由此n个待映射区间还可能存在一些参考点无法满足上述第一线性规划方程组的约束，使得已确定的系数值可能不是最优的系数值，基于此，在一种可能的实现方式中，上述将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式，可以包括：
[0099]
检测n个待映射区间中是否存在满足第一指定条件的极值点和边界点，第一指定条件包括：使已确定系数值的第k个第一初始多项式与标准化阶梯函数之间偏差的绝对值大于第一压缩率参数值与待映射区间的区间半径之间的乘积；
[0100]
在n个待映射区间中不存在满足第一指定条件的极值点和边界点的情况下，将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式；或，
[0101]
在n个待映射区间中存在满足第一指定条件的极值点和边界点的情况下，将满足第一指定条件的极值点和边界值添加到第一参考点集合中，得到第二参考点集合；根据第二参考点集合、第一多项式系数阈值以及标准化阶梯函数，重新确定第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为第k个第一逼近多项式。
[0102]
其中，上述第一指定条件可以表示为其中，代表已确定系数值的第k个第一初始多项式，代表标准化阶梯函数，c
l
代表第一压缩率参数值，基于此，检测n个待映射区间中是否存在满足第一指定条件的极值点和边界点，可以理解为，分别检测n个待映射区间中是否存在满足的极值点和边界点x
′
。
[0103]
其中，可以参照上述步骤s223中第k个第一初始多项式中系数的系数值的确定方式，实现根据第二参考点集合、第一多项式系数阈值以及标准化阶梯函数，重新确定第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为第k个第一逼近多项式，在此不做赘述。
[0104]
在一种可能的实现方式中，根据第二参考点集合、第一多项式系数阈值以及标准化阶梯函数，重新确定第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为第k个第一逼近多项式，可以包括：
[0105]
根据第二参考点集合、已确定系数值的第k个第一初始多项式、标准化阶梯函数以及第k个第一初始多项式对应的各个待映射区间的区间半径，确定各个待映射区间各自对应的实际区间压缩率中的最大压缩率；
[0106]
在第一压缩率参数值的加权值大于最大压缩率的情况下，根据第二参考点集合、第一多项式系数阈值以及标准化阶梯函数，重新确定第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式；或，
[0107]
在第一压缩率参数值的加权值小于或等于最大压缩率的情况下，将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式。
[0108]
可选地，可以采用公式(2)实现根据第二参考点集合χ
′
、已确定系数值的第k个第一初始多项式标准化阶梯函数以及第k个第一初始多项式对应的各个待映射区间的区间半径t
nk
，确定各个待映射区间各自对应的实际区间压缩率中的最大压缩率cu：
[0109][0110]
其中，第一压缩率参数值c
l
的加权值可以表示为(1+γ)c
l
，γ代表加权值也可称为近似因子，作为多项式逼近方法的终止条件，用户可以根据实现需求自定义设置该γ的具体数值，通过γ能够控制在第一压缩率参数值收敛的情况下，输出第k个第一初始多项式的系数值。基于此，若cu《(1+γ)c
l
，则输出已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式，若cu≥(1+γ)c
l
，则重新确定第k个第一初始多项式中系数的系数值。
[0111]
根据本公开实施例，能够有效计算出精度高、误差小的各个第一逼近多项式，从而得到与解题函数更逼近的复合多项式函数。
[0112]
图4示出根据本公开一实施例的一种多项式逼近方式的流程图，图4示出的多项式逼近方式可以用于确定任意阶梯函数对应的复合多项式函数中的第二逼近多项式，如图4所示，上述步骤s22确定与处理指令指示的阶梯函数逼近的复合多项式函数，可以包括：
[0113]
步骤s225，根据针对第二逼近多项式所设置的多项式次数，构建待确定系数值的第二初始多项式。
[0114]
在实际应用中，用户可以根据实际需求设置第二逼近多项式所具有的多项式次数；在已知用户设置的多项式次数后，可以从上述基多项式集合中选取至少一种基多项式，构建与该多项式次数匹配的第二初始多项式。其中，基多项式可以理解为构成初始多项式的基础项，例如，至少包括但不限于“d+ex”、“hx
2”、“mx
3”等基多项式。
[0115]
步骤s226，根据n个子区间各自的中点以及k个第一逼近多项式中的第k个第一逼近多项式输出的n个映射后区间的区间半径，确定第二初始多项式对应的n个待映射区间，并从第二初始多项式对应的n个待映射区间中选取多个参考点，得到第三参考点集合。
[0116]
其中，k个第一逼近多项式中的第k个第一逼近多项式输出的n个映射后区间的区间半径，可以理解为，k个第一逼近多项式中最后一个第一逼近多项式输出的n个映射后区间的区间半径。在实际应用中，可以将通过上述步骤s222确定出的第k个第一逼近多项式对应的的n个待映射区间输入至第k个第一逼近多项式，得到第k个第一逼近多项式输出的n个映射后区间，进而可以计算出该第k个第一逼近多项式输出的n个映射后区间各自的区间半径。
[0117]
示例性地，假设第k个第一逼近多项式输出的n个映射后区间各自的区间半径表示为t
1k
、t
2k
、
…
、t
nk
，n个子区间各自的中点表示为z1、z2、
…
、zn，则第二初始多项式对应的n个待映射区间可以表示为[z
1-t
1k
,z1+t
1k
]、[z
2-t
2k
,z2+t
2k
]、
…
、[z
n-t
nk
,zn+t
nk
]，或者可以表示为[z
n-t
nk
,zn+t
nk
],n∈[1,n]，也即，将n个子区间各自的中点作为n个映射后区间的中点，并基于n个映射后区间的中点和各自对应的区间半径，得到第二初始多项式对应的n个待映射区间。
[0118]
在一种可能的实现方式中，为了可以控制利用复合多项式函数执行同态计算的计算精度，还可以对各个待映射区间设置误差界ηk，并根据该误差界ηk、n个子区间各自的中点以及n个映射后区间的区间半径，确定第二初始多项式对应的n个待映射区间，例如，基于误差界ηk，上述第二初始多项式对应的n个待映射区间可以表示为：[z
1-t
1k-ηk,z1+t
1k
+ηk]、[z
2-t
2k-ηk,z2+t
2k
+ηk]、
…
、[z
n-t
nk-ηk,zn+t
nk
+ηk]，或者可以表示为[z
n-t
nk-ηk,zn+t
nk
+ηk],n∈[1,n]。其中，本领域技术人员可以根据实际需求自定设置误差界ηk的具体数值，ηk＞0，对此本公开实施例不作限制。
[0119]
在实际应用中，例如可以采用随机选取、递增选取、均匀选取等本领域已知的选取方式，实现从第二初始多项式对应的n个待映射区间中分别选取多个参考点，得到第三参考点集合，对此本公开实施例不作限制。应理解，本公开实施例对于参考点的选取方式和选取数量不作限制，也即对第三参考点集合中参考点的数量不作限制。
[0120]
步骤s227，根据第三参考点集合、预设的第二多项式系数阈值以及阶梯函数，确定第二初始多项式中系数的系数值，第二初始多项式中系数的最大系数值小于或等于第二多项式阈值。
[0121]
其中，用户根据实际需求设置第二多项式系数阈值的具体数值，对此本公开实施
例不作限制。通过设置第二多项式系数阈值，可以灵活控制所生成的复合多项式函数的系数上界，使其能够适用于不同精度的同态计算任务。
[0122]
在一种可能的实现方式中，根据第三参考点集合、预设的第二多项式系数阈值以及阶梯函数，确定第二初始多项式中系数的系数值，包括：
[0123]
构建第二初始多项式与阶梯函数之间的第二线性规划方程组，第二线性规划方程组用于约束第二初始多项式与阶梯函数之间偏差的绝对值小于或等于第二压缩率参数与第二初始多项式对应的各个待映射区间的区间半径之间的乘积，以及约束第二初始多项式中的最大系数小于或等于第二多项式系数阈值；
[0124]
以最小化第二压缩率参数为目标，将第三参考点集合中的各个参考点代入第二线性规划方程组，并求解代入各个参考点后的第二线性规划方程组，得到第二初始多项式中系数的系数值以及第二压缩率参数的第二压缩率参数值。
[0125]
示例性地，上述第二初始多项式g与阶梯函数κ之间的第二线性规划方程组，可以表示为公式(3)：
[0126][0127]
其中，χ
″
代表第三参考点集合，x
″
l
代表第三参考点集合中的任一参考点，κ代表阶梯函数，c
′
代表第二压缩率参数，tn代表第二初始多项式对应的n个待映射区间中的第n个待映射区间的区间半径，c
max
(g)代表第二初始多项式g的系数中的最大系数，b
′
代表第二多项式系数阈值。
[0128]
应理解，上述公式(3)中|g(x
″
l
)-κ(x
″
l
)|≤c
′
tn代表第二初始多项式与阶梯函数之间偏差的绝对值小于或等于第二压缩率参数与第二初始多项式对应的各个待映射区间的区间半径之间的乘积，上述c
max
(g)≤b
′
代表第二初始多项式中的最大系数小于或等于第二多项式系数阈值。通过求解上述第一线性规划方程组，相当于使得第一压缩率参数c达到最优也即最小，或者说，尽可能地让fk把待映射区间值映射到初始子区间中点附近更小的子区间上，且多项式系数小于设置的系数上界。
[0129]
在实际应用中，例如可以采用本领域任意已知的线性规划求解器或整数规划求解器等求解器，实现以最小化第二压缩率参数为目标，求解代入各个参考点后的第二线性规划方程组，得到第二初始多项式中系数的系数值以及第二压缩率参数的第二压缩率参数值，也即，本公开实施例对于上述第二线性规划方程组的求解方式不作限制，只要能求解出第二初始多项式中系数的系数值以及第二压缩率参数的第二压缩率参数值即可。
[0130]
步骤s228，将已确定系数值的第二初始多项式作为第二逼近多项式。
[0131]
在实际应用中，在得到二初始多项式中各个系数的系数值后，可以将已确定系数值的第二初始多项式作为第二逼近多项式。
[0132]
考虑到，上述步骤s226是利用从n个待映射区间中选取多个参考点所构成的第三参考点集合来确定的第二初始多项式中各个系数的系数值，由此n个待映射区间还可能存在一些参考点无法满足上述第二线性规划方程组的约束，使得已确定的系数值可能不是最优的系数值，基于此，在一种可能的实现方式中，上述将已确定系数值的第二初始多项式作为第二逼近多项式，可以包括：
[0133]
检测第二初始多项式对应的n个待映射区间中是否存在满足第二指定条件的极值
点和边界点，第二指定条件包括：使已确定系数值的第二初始多项式与阶梯函数之间偏差的绝对值大于第二压缩率参数值与第二初始多项式对应的待映射区间的区间半径之间的乘积；
[0134]
在第二初始多项式对应的n个待映射区间中不存在满足第二指定条件的极值点和边界点的情况下，将已确定系数值的第二初始多项式作为第二逼近多项式；或，
[0135]
在第二初始多项式对应的n个待映射区间中存在满足第二指定条件的极值点和边界点的情况下，将满足第二指定条件的极值点和边界值添加到第三参考点集合中，得到第四参考点集合；根据第四参考点集合、第二多项式系数阈值以及阶梯函数，重新确定第二初始多项式中系数的系数值，并将已重新确定系数值的第二初始多项式作为第二逼近多项式。
[0136]
其中，上述第二指定条件可以表示为其中，代表已确定系数值的第二初始多项式，κ代表阶梯函数，c
′
l
代表第二压缩率参数值，基于此，检测n个待映射区间中是否存在满足第一指定条件的极值点和边界点，可以理解为，分别检测n个待映射区间中是否存在满足的极值点和边界点。
[0137]
其中，可以参照上述步骤s227中第二初始多项式中系数的系数值的确定方式，实现根据第四参考点集合、第二多项式系数阈值以及阶梯函数，重新确定第二初始多项式中系数的系数值，并将已重新确定系数值的第二初始多项式作为第二逼近多项式，在此不做赘述。
[0138]
在一种可能的实现方式中，根据第四参考点集合、第二多项式系数阈值以及阶梯函数，重新确定第二初始多项式中系数的系数值，并将已重新确定系数值的第二初始多项式作为第二逼近多项式，可以包括：
[0139]
根据第四参考点集合、已确定系数值的第二初始多项式、阶梯函数以及第二初始多项式对应的各个待映射区间的区间半径，确定各个待映射区间各自对应的实际区间压缩率中的最大压缩率；
[0140]
在第二压缩率参数值的加权值大于最大压缩率的情况下，根据第四参考点集合、第二多项式系数阈值以及阶梯函数，重新确定第二初始多项式中系数的系数值，并将已重新确定系数值的第二初始多项式作为所述第二逼近多项式；或，
[0141]
在第二压缩率参数值的加权值小于或等于最大压缩率的情况下，将已确定系数值的第二初始多项式作为第二逼近多项式。
[0142]
可选地，可以采用公式(4)实现根据第四参考点集合χ
″′
、已确定系数值的第二初始多项式阶梯函数κ以及第二初始多项式对应的各个待映射区间的区间半径tn，确定各个待映射区间各自对应的实际区间压缩率中的最大压缩率c
′u：
[0143][0144]
其中，第二压缩率参数值c
′
l
的加权值可以表示为(1+γ
′
)c
′
l
，γ
′
代表加权值也可称为近似因子，作为多项式逼近方法的终止条件，用户可以根据实现需求自定义设置该γ
′
的具体数值，通过γ
′
可以控制在第二压缩率参数值收敛的情况下，输出第二初始多项式的系数值。基于此，若c
′u《(1+γ
′
)c
′
l
，则输出已确定系数值的第二初始多项式作为第二逼近多项式，若c
′u≥(1+γ
′
)c
′
l
，则重新确定第二初始多项式中系数的系数值。
[0145]
在一种可能的实现方式中，所述方法还包括：根据第二逼近多项式与阶梯函数的函数值之间偏差的最大值，以及预设的误差界，确定复合多项式函数的输出精度，误差界用于控制复合多项式函数的同态计算精度。通过该方式，可以便于用户知晓阶梯函数对应的复合多项式函的输出精度。
[0146]
其中，第二逼近多项式与阶梯函数的函数值之间偏差的最大值可以表示为：x∈u
′n，u
′n＝[z
n-t
nk-ηk,zn+t
nk
+ηk],n∈[1,n]，yn代表阶梯函数在区间u
′n处的函数值，基于此，可以通过公式(5)实现根据第二逼近多项式与阶梯函数的函数值之间偏差的最大值，以及预设的误差界ηg，确定复合多项式函数的输出精度2-α
。
[0147]
2-α
，α＝-log(t+ηg)(3)
[0148]
其中，本领域技术人员可以根据实际需求自定设置误差界ηg的具体数值，ηg＞0，对此本公开实施例不作限制。
[0149]
根据本公开实施例，能够有效计算出精度高、误差小的第二逼近多项式，从而得到与阶梯函数更逼近的复合多项式函数。
[0150]
图5示出根据本公开一实施例的同态密文处理装置的框图，如图5所示，该装置包括：
[0151]
获取模块501，用于获取终端发送的待处理的同态密文以及针对所述同态密文的处理指令，所述同态密文包括终端对用户数据的加密结果，所述处理指令用于指示处理所述同态密文所需的阶梯函数，所述阶梯函数的取值区间包括多个不同的初始子区间，所述阶梯函数在同一初始子区间的函数值相同；
[0152]
确定模块502，用于确定与所述处理指令指示的阶梯函数逼近的复合多项式函数，所述复合多项式函数包括多个第一逼近多项式与第二逼近多项式，所述多个第一逼近多项式用于将所述阶梯函数对应的各个初始子区间迭代映射到各个初始子区间中点附近的目标子区间，各个目标子区间的区间范围小于各个初始子区间的区间范围，所述第二逼近多项式用于将各个目标子区间映射到所述阶梯函数在各个初始子区间对应的函数值；
[0153]
执行模块503，用于利用所述复合多项式函数执行对所述同态密文的同态计算，得到密文处理结果，并将所述密文处理结果发送给所述终端。
[0154]
在一种可能的实现方式中，所述阶梯函数的取值区间包括n个初始子区间，所述复合多项式函数中包括k个第一逼近多项式，n和k为正整数，其中，所述确定与所述处理指令指示的阶梯函数逼近的复合多项式函数，包括：针对所述k个第一逼近多项式中的第k个第一逼近多项式，根据针对所述第k个第一逼近多项式所设置的多项式次数，构建待确定系数值的第k个第一初始多项式，1≤k≤k；基于所述阶梯函数对应的n个初始子区间，确定所述第k个第一初始多项式对应的n个待映射区间，并从所述第k个第一初始多项式对应的n个待映射区间中分别选取多个参考点，得到第一参考点集合；根据所述第一参考点集合、预设的第一多项式系数阈值以及所述阶梯函数对应的标准化阶梯函数，确定所述第k个第一初始多项式中系数的系数值，其中，所述第k个第一初始多项式中系数的最大系数值小于或等于所述第一多项式系数阈值，所述标准化阶梯函数的取值区间与所述阶梯函数相同，且所述标准化阶梯函数在第1个子区间的函数值为所述取值区间的左边界点、在第n个子区间的函数值为所述取值区间的右边界点以及在第i个子区间的函数值为第i个子区间的中点，1＜i＜n；将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式。
[0155]
在一种可能的实现方式中，所述基于所述阶梯函数对应的n个初始子区间，确定所述第k个第一初始多项式对应的n个待映射区间，包括：当k＝1时，根据所述n个初始子区间以及预设的输入精度，确定第1个第一初始多项式对应的n个待映射区间，所述输入精度表征所述复合多项式函数所具有的输入精度；当k≥k＞1时，将第k-1个第一初始多项式对应的n个待映射区间输入至第k-1个第一逼近多项式，得到所述第k-1个第一逼近多项式输出的n个映射后区间，并根据所述n个初始子区间各自的中点以及所述n个映射后区间的区间半径，确定所述第k个第一初始多项式对应的n个待映射区间。
[0156]
在一种可能的实现方式中，所述根据所述第一参考点集合、预设的第一多项式系数阈值以及所述阶梯函数对应的标准化阶梯函数，确定所述第k个第一初始多项式中系数的系数值，包括：构建所述第k个第一初始多项式与所述标准化阶梯函数之间的第一线性规划方程组，所述第一线性规划方程组用于约束所述第k个第一初始多项式与所述标准化阶梯函数之间偏差的绝对值小于或等于第一压缩率参数与各个待映射区间的区间半径之间的乘积，以及约束所述第k个第一初始多项式中的最大系数小于或等于所述第一多项式系数阈值；以最小化所述第一压缩率参数为目标，将所述第一参考点集合中的各个参考点代入所述第一线性规划方程组，并求解代入各个参考点后的第一线性规划方程组，得到所述第k个第一初始多项式中系数的系数值以及所述第一压缩率参数的第一压缩率参数值。
[0157]
在一种可能的实现方式中，所述将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式，包括：检测所述n个待映射区间中是否存在满足第一指定条件的极值点和边界点，所述第一指定条件包括：使已确定系数值的第k个第一初始多项式与所述标准化阶梯函数之间偏差的绝对值大于所述第一压缩率参数值与待映射区间的区间半径之间的乘积；在所述n个待映射区间中不存在满足所述第一指定条件的极值点和边界点的情况下，将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式；或，在所述n个待映射区间中存在满足所述第一指定条件的极值点和边界点的情况下，将满足所述第一指定条件的极值点和边界值添加到所述第一参考点集合中，得到第二参考点集合；根据所述第二参考点集合、所述第一多项式系数阈值以及所述标准化阶梯函数，重新确定所述第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式。
[0158]
在一种可能的实现方式中，所述根据第二参考点集合、所述第一多项式系数阈值以及所述标准化阶梯函数，重新确定所述第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式，包括：根据所述第二参考点集合、已确定系数值的第k个第一初始多项式、所述标准化阶梯函数以及所述第k个第一初始多项式对应的各个待映射区间的区间半径，确定各个待映射区间各自对应的实际区间压缩率中的最大压缩率；在所述第一压缩率参数值的加权值大于所述最大压缩率的情况下，根据所述第二参考点集合、所述第一多项式系数阈值以及所述标准化阶梯函数，重新确定所述第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式；或，在所述第一压缩率参数值的加权值小于或等于所述最大压缩率的情况下，将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式。
[0159]
在一种可能的实现方式中，所述确定与所述处理指令指示的阶梯函数逼近的复合
多项式函数，包括：根据针对所述第二逼近多项式所设置的多项式次数，构建待确定系数值的第二初始多项式；根据所述n个子区间各自的中点以及所述k个第一逼近多项式中的第k个第一逼近多项式输出的n个映射后区间的区间半径，确定所述第二初始多项式对应的n个待映射区间，并从所述第二初始多项式对应的n个待映射区间中选取多个参考点，得到第三参考点集合；根据所述第三参考点集合、预设的第二多项式系数阈值以及所述阶梯函数，确定所述第二初始多项式中系数的系数值，所述第二初始多项式中系数的最大系数值小于或等于所述第二多项式阈值；将已确定系数值的第二初始多项式作为第二逼近多项式。
[0160]
在一种可能的实现方式中，所述根据所述第三参考点集合、预设的第二多项式系数阈值以及所述阶梯函数，确定所述第二初始多项式中系数的系数值，包括：构建所述第二初始多项式与所述阶梯函数之间的第二线性规划方程组，所述第二线性规划方程组用于约束所述第二初始多项式与所述阶梯函数之间偏差的绝对值小于或等于第二压缩率参数与所述第二初始多项式对应的各个待映射区间的区间半径之间的乘积，以及约束所述第二初始多项式中的最大系数小于或等于所述第二多项式系数阈值；以最小化所述第二压缩率参数为目标，将所述第三参考点集合中的各个参考点代入所述第二线性规划方程组，并求解代入各个参考点后的第二线性规划方程组，得到所述第二初始多项式中系数的系数值以及所述第二压缩率参数的第二压缩率参数值。
[0161]
在一种可能的实现方式中，所述将已确定系数值的第二初始多项式作为第二逼近多项式，包括：检测所述第二初始多项式对应的n个待映射区间中是否存在满足第二指定条件的极值点和边界点，所述第二指定条件包括：使已确定系数值的第二初始多项式与所述阶梯函数之间偏差的绝对值大于所述第二压缩率参数值与第二初始多项式对应的待映射区间的区间半径之间的乘积；在所述第二初始多项式对应的n个待映射区间中不存在满足所述第二指定条件的极值点和边界点的情况下，将已确定系数值的第二初始多项式作为第二逼近多项式；或，在所述第二初始多项式对应的n个待映射区间中存在满足所述第二指定条件的极值点和边界点的情况下，将满足所述第二指定条件的极值点和边界值添加到所述第三参考点集合中，得到第四参考点集合；根据所述第四参考点集合、所述第二多项式系数阈值以及所述阶梯函数，重新确定所述第二初始多项式中系数的系数值，并将已重新确定系数值的第二初始多项式作为所述第二逼近多项式。
[0162]
在一种可能的实现方式中，所述装置还包括：输出精度确定模块，用于根据所述第二逼近多项式与所述阶梯函数的函数值之间偏差的最大值，以及预设的误差界，确定所述复合多项式函数的输出精度，所述误差界用于控制所述复合多项式函数的同态计算精度。
[0163]
根据本公开实施例，利用与处理同态密文所需的阶梯函数逼近的复合多项式函数，也即利用由多个第一逼近多项式和第二逼近多项式构成的复合多项式函数执行对同态密文的同态计算，能够提高对同态密文的同态计算效率和计算精度，满足各种应用场景的同态计算需求。
[0164]
在一些实施例中，本公开实施例提供的装置具有的功能或包含的模块可以用于执行上文方法实施例描述的方法，其具体实现可以参照上文方法实施例的描述，为了简洁，这里不再赘述。
[0165]
本公开实施例还提出一种计算机可读存储介质，其上存储有计算机程序指令，所述计算机程序指令被处理器执行时实现上述方法。计算机可读存储介质可以是易失性或非
易失性计算机可读存储介质。
[0166]
本公开实施例还提出一种电子设备，包括：处理器；用于存储处理器可执行指令的存储器；其中，所述处理器被配置为在执行所述存储器存储的指令时，实现上述方法。
[0167]
本公开实施例还提供了一种计算机程序产品，包括计算机可读代码，或者承载有计算机可读代码的非易失性计算机可读存储介质，当所述计算机可读代码在电子设备的处理器中运行时，所述电子设备中的处理器执行上述方法。
[0168]
图6示出根据本公开一实施例的一种电子设备1900的框图。例如，电子设备1900可以被提供为一服务器或终端设备。参照图6，电子设备1900包括处理组件1922，其进一步包括一个或多个处理器，以及由存储器1932所代表的存储器资源，用于存储可由处理组件1922的执行的指令，例如应用程序。存储器1932中存储的应用程序可以包括一个或一个以上的每一个对应于一组指令的模块。此外，处理组件1922被配置为执行指令，以执行上述方法。
[0169]
电子设备1900还可以包括一个电源组件1926被配置为执行电子设备1900的电源管理，一个有线或无线网络接口1950被配置为将电子设备1900连接到网络，和一个输入输出接口1958(i/o接口)。电子设备1900可以操作基于存储在存储器1932的操作系统，例如windows server
tm
，mac os x
tm
，unix
tm
,linux
tm
，freebsd
tm
或类似。
[0170]
在示例性实施例中，还提供了一种非易失性计算机可读存储介质，例如包括计算机程序指令的存储器1932，上述计算机程序指令可由电子设备1900的处理组件1922执行以完成上述方法。
[0171]
本公开可以是系统、方法和/或计算机程序产品。计算机程序产品可以包括计算机可读存储介质，其上载有用于使处理器实现本公开的各个方面的计算机可读程序指令。
[0172]
计算机可读存储介质可以是可以保持和存储由指令执行设备使用的指令的有形设备。计算机可读存储介质例如可以是――但不限于――电存储设备、磁存储设备、光存储设备、电磁存储设备、半导体存储设备或者上述的任意合适的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：便携式计算机盘、硬盘、随机存取存储器(ram)、只读存储器(rom)、可擦式可编程只读存储器(eprom或闪存)、静态随机存取存储器(sram)、便携式映射盘只读存储器(cd-rom)、数字多功能盘(dvd)、记忆棒、软盘、机械编码设备、例如其上存储有指令的打孔卡或凹槽内凸起结构、以及上述的任意合适的组合。这里所使用的计算机可读存储介质不被解释为瞬时信号本身，诸如无线电波或者其他自由传播的电磁波、通过波导或其他传输媒介传播的电磁波(例如，通过光纤电缆的光脉冲)、或者通过电线传输的电信号。
[0173]
这里所描述的计算机可读程序指令可以从计算机可读存储介质下载到各个计算/处理设备，或者通过网络、例如因特网、局域网、广域网和/或无线网下载到外部计算机或外部存储设备。网络可以包括铜传输电缆、光纤传输、无线传输、路由器、防火墙、交换机、网关计算机和/或边缘服务器。每个计算/处理设备中的网络适配卡或者网络接口从网络接收计算机可读程序指令，并转发该计算机可读程序指令，以供存储在各个计算/处理设备中的计算机可读存储介质中。
[0174]
用于执行本公开操作的计算机程序指令可以是汇编指令、指令集架构(isa)指令、机器指令、机器相关指令、微代码、固件指令、状态设置数据、或者以一种或多种编程语言的
任意组合编写的源代码或目标代码，所述编程语言包括面向对象的编程语言—诸如smalltalk、c++等，以及常规的过程式编程语言—诸如“c”语言或类似的编程语言。计算机可读程序指令可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络—包括局域网(lan)或广域网(wan)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。在一些实施例中，通过利用计算机可读程序指令的状态信息来个性化定制电子电路，例如可编程逻辑电路、现场可编程门阵列(fpga)或可编程逻辑阵列(pla)，该电子电路可以执行计算机可读程序指令，从而实现本公开的各个方面。
[0175]
这里参照根据本公开实施例的方法、装置(系统)和计算机程序产品的流程图和/或框图描述了本公开的各个方面。应当理解，流程图和/或框图的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机可读程序指令实现。
[0176]
这些计算机可读程序指令可以提供给通用计算机、专用计算机或其它可编程数据处理装置的处理器，从而生产出一种机器，使得这些指令在通过计算机或其它可编程数据处理装置的处理器执行时，产生了实现流程图和/或框图中的一个或多个方框中规定的功能/动作的装置。也可以把这些计算机可读程序指令存储在计算机可读存储介质中，这些指令使得计算机、可编程数据处理装置和/或其他设备以特定方式工作，从而，存储有指令的计算机可读介质则包括一个制造品，其包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的各个方面的指令。
[0177]
也可以把计算机可读程序指令加载到计算机、其它可编程数据处理装置、或其它设备上，使得在计算机、其它可编程数据处理装置或其它设备上执行一系列操作步骤，以产生计算机实现的过程，从而使得在计算机、其它可编程数据处理装置、或其它设备上执行的指令实现流程图和/或框图中的一个或多个方框中规定的功能/动作。
[0178]
附图中的流程图和框图显示了根据本公开的多个实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或指令的一部分，所述模块、程序段或指令的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。
[0179]
以上已经描述了本公开的各实施例，上述说明是示例性的，并非穷尽性的，并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易见的。本文中所用术语的选择，旨在最好地解释各实施例的原理、实际应用或对市场中的技术改进，或者使本技术领域的其它普通技术人员能理解本文披露的各实施例。

技术特征：
1.一种同态密文处理方法，其特征在于，所述方法应用于服务器，包括：获取终端发送的待处理的同态密文以及针对所述同态密文的处理指令，所述同态密文包括终端对用户数据的加密结果，所述处理指令用于指示处理所述同态密文所需的阶梯函数，所述阶梯函数的取值区间包括多个不同的初始子区间，所述阶梯函数在同一初始子区间的函数值相同；确定与所述处理指令指示的阶梯函数逼近的复合多项式函数，所述复合多项式函数包括多个第一逼近多项式与第二逼近多项式，所述多个第一逼近多项式用于将所述阶梯函数对应的各个初始子区间迭代映射到各个初始子区间中点附近的目标子区间，各个目标子区间的区间范围小于各个初始子区间的区间范围，所述第二逼近多项式用于将各个目标子区间映射到所述阶梯函数在各个初始子区间对应的函数值；利用所述复合多项式函数执行对所述同态密文的同态计算，得到密文处理结果，并将所述密文处理结果发送给所述终端。2.根据权利要求1所述的方法，其特征在于，所述阶梯函数的取值区间包括n个初始子区间，所述复合多项式函数中包括k个第一逼近多项式，n和k为正整数，其中，所述确定与所述处理指令指示的阶梯函数逼近的复合多项式函数，包括：针对所述k个第一逼近多项式中的第k个第一逼近多项式，根据针对所述第k个第一逼近多项式所设置的多项式次数，构建待确定系数值的第k个第一初始多项式，1≤k≤k；基于所述阶梯函数对应的n个初始子区间，确定所述第k个第一初始多项式对应的n个待映射区间，并从所述第k个第一初始多项式对应的n个待映射区间中分别选取多个参考点，得到第一参考点集合；根据所述第一参考点集合、预设的第一多项式系数阈值以及所述阶梯函数对应的标准化阶梯函数，确定所述第k个第一初始多项式中系数的系数值，其中，所述第k个第一初始多项式中系数的最大系数值小于或等于所述第一多项式系数阈值，所述标准化阶梯函数的取值区间与所述阶梯函数相同，且所述标准化阶梯函数在第1个子区间的函数值为所述取值区间的左边界点、在第n个子区间的函数值为所述取值区间的右边界点以及在第i个子区间的函数值为第i个子区间的中点，1＜i＜n；将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式。3.根据权利要求2所述的方法，其特征在于，所述基于所述阶梯函数对应的n个初始子区间，确定所述第k个第一初始多项式对应的n个待映射区间，包括：当k＝1时，根据所述n个初始子区间以及预设的输入精度，确定第1个第一初始多项式对应的n个待映射区间，所述输入精度表征所述复合多项式函数所具有的输入精度；当k≥k＞1时，将第k-1个第一初始多项式对应的n个待映射区间输入至第k-1个第一逼近多项式，得到所述第k-1个第一逼近多项式输出的n个映射后区间，并根据所述n个初始子区间各自的中点以及所述n个映射后区间的区间半径，确定所述第k个第一初始多项式对应的n个待映射区间。4.根据权利要求2所述的方法，其特征在于，所述根据所述第一参考点集合、预设的第一多项式系数阈值以及所述阶梯函数对应的标准化阶梯函数，确定所述第k个第一初始多项式中系数的系数值，包括：构建所述第k个第一初始多项式与所述标准化阶梯函数之间的第一线性规划方程组，
所述第一线性规划方程组用于约束所述第k个第一初始多项式与所述标准化阶梯函数之间偏差的绝对值小于或等于第一压缩率参数与各个待映射区间的区间半径之间的乘积，以及约束所述第k个第一初始多项式中的最大系数小于或等于所述第一多项式系数阈值；以最小化所述第一压缩率参数为目标，将所述第一参考点集合中的各个参考点代入所述第一线性规划方程组，并求解代入各个参考点后的第一线性规划方程组，得到所述第k个第一初始多项式中系数的系数值以及所述第一压缩率参数的第一压缩率参数值。5.根据权利要求4所述的方法，其特征在于，所述将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式，包括：检测所述n个待映射区间中是否存在满足第一指定条件的极值点和边界点，所述第一指定条件包括：使已确定系数值的第k个第一初始多项式与所述标准化阶梯函数之间偏差的绝对值大于所述第一压缩率参数值与待映射区间的区间半径之间的乘积；在所述n个待映射区间中不存在满足所述第一指定条件的极值点和边界点的情况下，将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式；或，在所述n个待映射区间中存在满足所述第一指定条件的极值点和边界点的情况下，将满足所述第一指定条件的极值点和边界值添加到所述第一参考点集合中，得到第二参考点集合；根据所述第二参考点集合、所述第一多项式系数阈值以及所述标准化阶梯函数，重新确定所述第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式。6.根据权利要求4所述的方法，其特征在于，所述根据第二参考点集合、所述第一多项式系数阈值以及所述标准化阶梯函数，重新确定所述第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式，包括：根据所述第二参考点集合、已确定系数值的第k个第一初始多项式、所述标准化阶梯函数以及所述第k个第一初始多项式对应的各个待映射区间的区间半径，确定各个待映射区间各自对应的实际区间压缩率中的最大压缩率；在所述第一压缩率参数值的加权值大于所述最大压缩率的情况下，根据所述第二参考点集合、所述第一多项式系数阈值以及所述标准化阶梯函数，重新确定所述第k个第一初始多项式中系数的系数值，并将已重新确定系数值的第k个第一初始多项式作为所述第k个第一逼近多项式；或，在所述第一压缩率参数值的加权值小于或等于所述最大压缩率的情况下，将已确定系数值的第k个第一初始多项式作为第k个第一逼近多项式。7.根据权利要求2至6任一项所述的方法，其特征在于，所述确定与所述处理指令指示的阶梯函数逼近的复合多项式函数，包括：根据针对所述第二逼近多项式所设置的多项式次数，构建待确定系数值的第二初始多项式；根据所述n个子区间各自的中点以及所述k个第一逼近多项式中的第k个第一逼近多项式输出的n个映射后区间的区间半径，确定所述第二初始多项式对应的n个待映射区间，并从所述第二初始多项式对应的n个待映射区间中选取多个参考点，得到第三参考点集合；根据所述第三参考点集合、预设的第二多项式系数阈值以及所述阶梯函数，确定所述第二初始多项式中系数的系数值，所述第二初始多项式中系数的最大系数值小于或等于所
述第二多项式阈值；将已确定系数值的第二初始多项式作为第二逼近多项式。8.根据权利要求7所述的方法，其特征在于，所述根据所述第三参考点集合、预设的第二多项式系数阈值以及所述阶梯函数，确定所述第二初始多项式中系数的系数值，包括：构建所述第二初始多项式与所述阶梯函数之间的第二线性规划方程组，所述第二线性规划方程组用于约束所述第二初始多项式与所述阶梯函数之间偏差的绝对值小于或等于第二压缩率参数与所述第二初始多项式对应的各个待映射区间的区间半径之间的乘积，以及约束所述第二初始多项式中的最大系数小于或等于所述第二多项式系数阈值；以最小化所述第二压缩率参数为目标，将所述第三参考点集合中的各个参考点代入所述第二线性规划方程组，并求解代入各个参考点后的第二线性规划方程组，得到所述第二初始多项式中系数的系数值以及所述第二压缩率参数的第二压缩率参数值。9.根据权利要求8所述的方法，其特征在于，所述将已确定系数值的第二初始多项式作为第二逼近多项式，包括：检测所述第二初始多项式对应的n个待映射区间中是否存在满足第二指定条件的极值点和边界点，所述第二指定条件包括：使已确定系数值的第二初始多项式与所述阶梯函数之间偏差的绝对值大于所述第二压缩率参数值与第二初始多项式对应的待映射区间的区间半径之间的乘积；在所述第二初始多项式对应的n个待映射区间中不存在满足所述第二指定条件的极值点和边界点的情况下，将已确定系数值的第二初始多项式作为第二逼近多项式；或，在所述第二初始多项式对应的n个待映射区间中存在满足所述第二指定条件的极值点和边界点的情况下，将满足所述第二指定条件的极值点和边界值添加到所述第三参考点集合中，得到第四参考点集合；根据所述第四参考点集合、所述第二多项式系数阈值以及所述阶梯函数，重新确定所述第二初始多项式中系数的系数值，并将已重新确定系数值的第二初始多项式作为所述第二逼近多项式。10.根据权利要求7所述的方法，其特征在于，所述方法还包括：根据所述第二逼近多项式与所述阶梯函数的函数值之间偏差的最大值，以及预设的误差界，确定所述复合多项式函数的输出精度，所述误差界用于控制所述复合多项式函数的同态计算精度。11.一种同态密文处理装置，其特征在于，所述装置应用于服务器，包括：获取模块，用于获取终端发送的待处理的同态密文以及针对所述同态密文的处理指令，所述同态密文包括终端对用户数据的加密结果，所述处理指令用于指示处理所述同态密文所需的阶梯函数，所述阶梯函数的取值区间包括多个不同的初始子区间，所述阶梯函数在同一初始子区间的函数值相同；确定模块，用于确定与所述处理指令指示的阶梯函数逼近的复合多项式函数，所述复合多项式函数包括多个第一逼近多项式与第二逼近多项式，所述多个第一逼近多项式用于将所述阶梯函数对应的各个初始子区间迭代映射到各个初始子区间中点附近的目标子区间，各个目标子区间的区间范围小于各个初始子区间的区间范围，所述第二逼近多项式用于将各个目标子区间映射到所述阶梯函数在各个初始子区间对应的函数值；执行模块，用于利用所述复合多项式函数执行对所述同态密文的同态计算，得到密文
处理结果，并将所述密文处理结果发送给所述终端。12.一种电子设备，其特征在于，包括：处理器；用于存储处理器可执行指令的存储器；其中，所述处理器被配置为在执行所述存储器存储的指令时，实现权利要求1至10中任意一项所述的方法。13.一种非易失性计算机可读存储介质，其上存储有计算机程序指令，其特征在于，所述计算机程序指令被处理器执行时实现权利要求1至10中任意一项所述的方法。

技术总结
本公开涉及同态密文处理方法、装置、电子设备及存储介质，所述方法包括：获取终端发送的待处理的同态密文以及针对同态密文的处理指令；确定与处理指令指示的阶梯函数逼近的复合多项式函数；利用复合多项式函数执行对同态密文的同态计算，得到密文处理结果，并将密文处理结果发送给终端。根据本公开实施例，能够有效提高对加密后的用户数据执行同态计算的计算效率和计算精度。计算效率和计算精度。计算效率和计算精度。


技术研发人员：黄泰榕 王安宇 马世和 王小云
受保护的技术使用者：清华大学
技术研发日：2023.06.16
技术公布日：2023/8/6