一种基于全同态加密的密文同态比较方法和装置

1.本发明涉及密文数据处理技术领域，更具体的说是涉及一种基于全同态加密的密文同态比较方法和装置。


背景技术：

2.同态加密允许对加密的数据执行算术操作，能够在不访问密钥的情况下计算加密的数据，并解密得到与明文下操作对应的结果。
3.在同态加密领域，完全同态加密因既满足乘法同态又满足加法同态而广受科学家的关注，并广泛应用于各种领域，如金融、医疗和基因组学；
4.然而，基于两种算术运算来实现的应用程序的数量是有限的。对于一些需要非算数运算的应用程序，通常使用比较运算，如k-means聚类、top-k数据操作和支持向量机。
5.目前，在加密数据上使用较多的是同态比较运算，即利用同态密码使用符号函数多项式近似处理加密信息，故在对同态密码中数据的进行比较时，出现了寻找符号函数的最佳近似的多项式的问题，为了更加近似加密信息，已经使用了各种方法，包括第一类的切比雪夫多项式，人工神经网络，最小二乘，newton
–
raphson等。
6.但上述方法计算效率较低，随着精度的提高对同态乘法的次数要求也更高，不仅会大大增加计算的时间消耗，在深度消耗和计算复杂度方面也暴露出日渐明显的问题。


技术实现要素：

7.有鉴于此，本发明提供了一种基于全同态加密的密文同态比较方法和装置，目的在于满足精度要求的情况下，降低深度消耗和计算复杂度，减少时间消耗以及提高计算效率。
8.为了实现上述目的，本发明采用如下技术方案：
9.一方面，本发明公开了一种基于全同态加密的密文同态比较方法，包括，
10.根据输入精度和输出精度，按如下公式确定分量多项式；
[0011][0012]
其中,，为输入精度，为第t个多项式的输出精度，为第t个多项式，表达式为，和为多项式的系数；
[0013]
根据所述分量多项式确定待比较明文对应符号函数的近似值。
[0014]
作为优选，初始化多项式使其满足在0处导数最大，使得，并由此确定多项式的系数和；
[0015]
其中，并且极大值点的函数值为1；为输入精度，为输出精度，为多项式，表达式为。
[0016]
作为优选，求解多项式系数的方程组为：
[0017][0018]
式中，为第i个多项式的输出精度，和为第i个多项式的系数。
[0019]
作为优选，所述分量多项式的次数n固定为3。
[0020]
作为优选，根据所述分量多项式确定待比较明文对应符号函数的近似值的过程包括：
[0021]
对待比较明文进行加密，得到加密密文后进行同态计算，获得分量多项式的输入密文；
[0022]
将所述输入密文代入所述分量多项式进行同态运算，得到待比较明文差值对应的符号函数近似值。
[0023]
作为优选，所述待比较明文进行加密前缩放至[0,1]区间范围内。
[0024]
作为优选，对加密密文进行同态计算的过程为：
[0025]
将第一待比较明文的密文与-1的密文执行乘法同态操作，所得结果与第二待比较明文的密文执行加法同态操作，得到第一和第二待比较明文差值的密文，所述第一和第二待比较明文差值的密文为同态比较的输入密文。
[0026]
作为优选，按如下公式，根据待比较明文对应符号函数的近似值得到待比较明文的密文结果；
[0027][0028]
式中，为多项式复合运算结果，x为多项式的输入密文。
[0029]
另一方面，本发明公开了一种基于全同态加密的密文同态比较装置，包括，
[0030]
分量多项式确定单元，用于根据输入精度和输出精度，按如下公式确定分量多项式；多项式的系数和；
[0031][0032]
其中,，为输入精度，为第t个多项式的输出精度，为第t个多项式，表达式为，和为多项式的系数；
[0033]
符号函数的近似值确定单元，用于根据所述分量多项式确定待比较明文对应符号函数的近似值。
[0034]
作为优选，还包括
[0035]
密文结果获取单元，用于根据如下公式，根据待比较明文对应符号函数的近似值得到待比较明文的密文结果；
[0036][0037]
式中，为多项式复合运算结果，x为多项式的输入密文。
[0038]
经由上述的技术方案可知，与现有技术相比，本发明公开提供了一种基于全同态加密的密文同态比较方法和装置，本发明基于输入精度和输出精度动态生成多个多项式，
并基于该多项式进行复合运算，使其逼近符号函数，从而实现近似比较函数的效果。
[0039]
本发明公开的同态比较近似方法在深度消耗和计算复杂性方面具有最优性，可有效减少同态乘法和加法次数，并需要更少的平摊运行时间，更适用于数据量大的应用场景。
[0040]
本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。本发明的目的和其他优点可通过在所写的说明书、权利要求书、以及附图中所特别指出的结构来实现和获得。
[0041]
下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。
附图说明
[0042]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。
[0043]
图1附图为本发明基于全同态加密的同态比较方法流程图；
[0044]
图2为动态多项式生成过程中分量多项式的部分图像；其中图（a）为第i个分量多项式的图像，图（b）为i+1个分量多项式的图像，图（c）为第i+2个分量多项式的图像；
[0045]
图3为分量多项式依次复合后得到的符号函数近似图像；图（a）为分量多项式复合t-4次生成的多项式函数图，图（b）为分量多项式复合t次生成的多项式函数图；
[0046]
图4为本发明提供的基于全同态加密的同态比较方法实现的具体流程图。
具体实施方式
[0047]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0048]
为提高计算效率，减少同态运算次数，本发明实施例提供了一种利用动态多项式复合逼近符号函数来近似比较函数的新方法。具体的，本发明通过如下方案实现。
[0049]
实施例一
[0050]
本实施例公开了一种基于全同态加密的密文同态比较方法，包括：
[0051]
首先，根据输入精度和输出精度，按如下公式确定分量多项式；
[0052][0053]
其中,，为输入精度，为第t个多项式的输出精度，为第t个多项式，表达式为，和为多项式的系数；
[0054]
其次，根据所述分量多项式确定待比较明文对应符号函数的近似值。
[0055]
整体来说，本发明方法分为分量多项式动态生成部分和密文状态下的多项式复合运算部分。
[0056]
具体的，本实施例中，分量多项式动态生成部分，是根据用户给定的输入精度和输出精度要求，利用输入精度给定初始多项式，不断更新被映射区间动态求解新的分量多项
式，直到最后的映射区间达到输出精度要求。
[0057]
其中，输入精度是指a-b差值的最小边界，输出精度是指a-b差值最终映射到的区间范围的最小边界值。
[0058]
生成步骤包括：
[0059]
首先，初始化多项式使其满足在0处导数最大，使得，并由此确定多项式系数和；
[0060]
其中，并且极大值点的函数值为1；为输入精度，为输出精度，为多项式，表达式为。
[0061]
本发明中已知两个等式关系，两个未知量可以精确求得，由于次数过高需要使用多项式逼近remez算法近似求得，且为满足奇函数的性质，需要使多项式的次数为奇数次方。
[0062]
为了精确求解多项式，本实施例中，确定每个分量多项式的最高次数为3，此时多项式的形式为；
[0063]
根据关系式，得到的求解多项式系数的方程组为：
[0064][0065]
式中，为第i个多项式的输出精度，和为第i个多项式的系数。
[0066]
进一步，
[0067]
计算多项式，使得，其中，求得新的多项式系数和；
[0068]
计算多项式，使得，其中，同样计算出新的多项式系数和；
[0069]
按照同样步骤进行，最终计算出多项式，满足，其中，以区间缩小到满足精度要求作为终止条件，使得，最终生成一组数量有限的度为3的多项式。
[0070]
动态生成的部分分量多项式的过程如图2所示，这里需要注意的是图像中的区间边界使用t来表示。函数的更新过程从另一种角度看可以理解为区间的映射过程，只需保证区间的映射范围ti至1是逐步缩小的，就可以在有限步的迭代之后得到在误差精度范围内的计算结果，从图像中可以看到前一个分量多项式的t作为下一个分量多项式的。
[0071]
对于密文状态下多项式复合运算部分，即根据所述分量多项式确定待比较明文对应符号函数的近似值；过程包括：
[0072]
首先对输入明文数据使用全同态加密方案进行加密，接着利用同态加和同态乘运算方法进行多项式计算，按照分量多项式顺序依次运算，求得符号函数近似值的密文输出，根据符号函数和比较函数的等式关系计算密文结果，最后对密文进行全同态方案的解密操
作得到最终的明文比较结果。
[0073]
具体步骤如下：
[0074]
第一步、对待比较明文进行加密，得到加密密文后进行同态计算，获得分量多项式的输入密文；
[0075]
本实施例中，给定待比较的两个明文即a和b，并判断明文的大小；
[0076]
本发明中，将待比较明文进行加密前缩放至[0,1]区间范围内；以保证两个明文的差在区间[-1,1]，从而符合符号函数的定义域[-1,1]；
[0077]
即当明文输入范围在区间[0,1]当中，直接作为明文输入执行加密操作；
[0078]
如果待比较的明文数据太大，首先需要对两个数据同时除以，使其缩放后在区间[0,1]范围内，之后作为明文输入执行加密操作；
[0079]
本技术采用支持浮点数近似计算的ckks全同态加密方案对明文进行加密，即给定安全参数，调用密钥生成算法，生成私钥sk，公钥pk，计算密钥evk；
[0080]
进一步，调用enc方法，用户使用公钥pk，对需要进行同态比较计算的两个明文输入a和b的明文多项式m1和m2分别进行全同态加密，得到的密文分别为和。
[0081]
本发明进行同态计算的步骤包括：
[0082]
将第一待比较明文的密文与-1的密文执行乘法同态操作，所得结果与第二待比较明文的密文执行加法同态操作，得到第一和第二待比较明文差值的密文，所述第一和第二待比较明文差值的密文为同态比较的输入密文。
[0083]
加同态运算，对于消息m1和m2的密文和，使用评估密钥evk进行计算，输出m1+m2对应的密文；
[0084]
乘同态运算，对于消息m1和m2的密文和，使用评估密钥evk进行计算，输出m1*m2对应的密文；
[0085]
本实施例中，对明文b的密文与-1的密文执行乘法同态操作，得到密文-；
[0086]
用明文a的密文与密文-执行加同态，得到差值a-b的密文，将此差值作为多项式的输入密文。
[0087]
第二步、将输入密文代入分量多项式进行同态运算，得到待比较明文差值对应的符号函数近似值。
[0088]
该步骤中，根据生成的多项式组，将输入密文带入分量多项式进行同态运算，按照生成的多项式顺序进行依次复合运算，得到多项式复合运算结果，并将该结果作为输入密文的符号函数对应密文结果，具体包括以下步骤：
[0089]
使用生成的多项式组，就可以得，，...，。
[0090]
将待比较明文缩放后的数值a和b对应的密文的差值带入多项式执行同
态操作进行复合运算，也就是计算复合多项式；
[0091]
多项式计算结束后输出一个密文，该密文即为明文下a-b对应符号函数sign(a-b)对应的密文近似值，记为；
[0092]
图3显示了分量多项式进行复合之后的函数图，左边的图显示了的函数图像，可以看到其图像是在某一区间范围内波动的，右边的图显示了的函数图像，h
t
是最终的近似函数图，接近符号函数。两个图作比较，可见，区间u
t
至1是缩小的，说明最终近似结果的精度是逐渐缩小的。
[0093]
将零处的邻域排除在外，可以观察到多项式复合t次的与符号函数的图像几乎一致。
[0094]
为了进一步优化上述技术方案，本实施例中，按如下公式，根据待比较明文对应符号函数的近似值得到待比较明文的密文结果；
[0095][0096]
式中，为多项式复合运算结果，x为多项式的输入密文。
[0097]
其中，推导过程为：
[0098]
比较运算和符号函数记为：
[0099]
,
[0100]
比较函数和符号函数有如下等式关系；
[0101]
，
[0102]
根据近似等式，可以得到如下公式：
[0103][0104]
于是就可以得到本技术中新的比较算法newcomph；
[0105]
将上一步中的计算结果进行同态加add和同态乘mult操作，即执行在密文下的运算；
[0106]
输出同态比较操作的密文结果ct。
[0107]
为了进一步优化上述技术方案，
[0108]
使用私钥对密文结果进行解密，得到所述明文对应的比较结果，具体包括以下步骤：
[0109]
用户使用私钥sk对执行结束后输出的密文ct进行解密，执行算法，得到ct解密后的消息m，这里m也就是对应明文下执行比较运算的结果的近似值，这里使用的解密方案是ckks全同态加密方案的解密算法dec。
[0110]
本实施例中，完整的全同态加密同态比较方法实现的具体方式流程，如图3所示，总体如下：
[0111]
s1、对明文数据加密：对待比较明文进行加密，获得明文的加密密文；对明文对应的加密密文进行同态计算，获得输入密文；
[0112]
s2、动态生成多项式组：给定输入精度和输出精度，不断更新参数，求解多项式系数，最终动态生成一组分量多项式；
[0113]
s3、多项式符合近似符号函数：根据生成的多项式组，将输入密文带入分量多项式进行同态运算，按照生成的多项式顺序进行依次复合运算，得到多项式复合运算结果，作为输入密文的符号函数对应密文结果；
[0114]
s4、获得比较结果密文：利用符号函数与比较函数对应的等式关系，对得到的密文结果进行同态计算，得到同态比较的密文结果；
[0115]
s5、对密文结果解密：使用私钥对密文结果进行解密，得到所述明文对应的比较结果。
[0116]
本发明利用动态多项式复合逼近符号函数来近似比较函数的方法，可有效克服现有技术中的问题，从而降低计算复杂性，减少同态运算次数，减少计算时间。
[0117]
实施例二
[0118]
本实施例公开了一种基于全同态加密的密文同态比较装置，包括，
[0119]
分量多项式确定单元，用于根据输入精度和输出精度，按如下公式确定分量多项式；
[0120][0121]
其中,，为输入精度，为第t个多项式的输出精度，为第t个多项式，表达式为，和为多项式的系数；
[0122]
符号函数的近似值确定单元，用于根据所述分量多项式确定待比较明文对应符号函数的近似值。
[0123]
一种实施例中，还包括
[0124]
密文结果获取单元，用于根据如下公式，根据待比较明文对应符号函数的近似值得到待比较明文的密文结果；
[0125][0126]
式中，为多项式复合运算结果，x为多项式的输入密文。
[0127]
实施例三
[0128]
本实施例公开了一种基于全同态加密的密文同态比较芯片，其中芯片中安装有基于全同态加密的密文同态比较装置，并执行如下完整的同态比较算法；
[0129]
s1、对待比较明文进行加密，获得所述明文的加密密文；
[0130]
s2、对所述明文对应的密文进行同态计算，获得输入密文；
[0131]
s3、给定输入精度和输出精度，不断更新参数，求解多项式系数，最终动态生成一组分量多项式；
[0132]
s4、根据生成的多项式组，将输入密文带入分量多项式进行同态运算，按照生成的多项式顺序进行依次复合运算，得到多项式复合运算结果，作为输入密文的符号函数对应密文结果；
[0133]
s5、利用符号函数与比较函数对应的等式关系，对得到的密文结果进行同态计算，得到同态比较的密文结果；
[0134]
s6、使用私钥对密文结果进行解密，得到所述明文对应的比较结果。
[0135]
本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的装置而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。
[0136]
对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。

技术特征：
1.一种基于全同态加密的密文同态比较方法，其特征在于，包括：根据输入精度和输出精度，按如下公式确定分量多项式；；其中,，为输入精度，为第t个多项式的输出精度，为第t个多项式，表达式为，和为多项式的系数；根据所述分量多项式确定待比较明文对应符号函数的近似值。2.根据权利要求1所述的一种基于全同态加密的密文同态比较方法，其特征在于，初始化多项式使其满足在0处导数最大，使得，并由此确定多项式的系数和；其中，并且极大值点的函数值为1；为输入精度，为输出精度，为多项式，表达式为。3.根据权利要求1或2所述的一种基于全同态加密的密文同态比较方法，其特征在于，求解多项式系数的方程组为：；式中，为第i个多项式的输出精度，和为第i个多项式的系数。4.根据权利要求1或2所述的一种基于全同态加密的密文同态比较方法，其特征在于，所述分量多项式的次数n固定为3。5.根据权利要求1所述的一种基于全同态加密的密文同态比较方法，其特征在于，根据所述分量多项式确定待比较明文对应符号函数的近似值的过程包括：对待比较明文进行加密，得到加密密文后进行同态计算，获得分量多项式的输入密文；将所述输入密文代入所述分量多项式进行同态运算，得到待比较明文差值对应的符号函数近似值。6.根据权利要求5所述的一种基于全同态加密的密文同态比较方法，其特征在于，所述待比较明文进行加密前缩放至[0,1]区间范围内。7.根据权利要求5所述的一种基于全同态加密的密文同态比较方法，其特征在于，对加密密文进行同态计算的过程为：将第一待比较明文的密文与-1的密文执行乘法同态操作，所得结果与第二待比较明文的密文执行加法同态操作，得到第一和第二待比较明文差值的密文，所述第一和第二待比较明文差值的密文为同态比较的输入密文。8.根据权利要求1所述的一种基于全同态加密的密文同态比较方法，其特征在于，按如下公式，根据待比较明文对应符号函数的近似值得到待比较明文的密文结果；；式中，为多项式复合运算结果，x为多项式的输入密文。
9.一种基于全同态加密的密文同态比较装置，其特征在于，包括，分量多项式确定单元，用于根据输入精度和输出精度，按如下公式确定分量多项式；多项式的系数和；；其中,，为输入精度，为第t个多项式的输出精度，为第t个多项式，表达式为，和为多项式的系数；符号函数的近似值确定单元，用于根据所述分量多项式确定待比较明文对应符号函数的近似值。10.根据权利要求9所述的一种基于全同态加密的密文同态比较装置，其特征在于，还包括，密文结果获取单元，用于根据如下公式，根据待比较明文对应符号函数的近似值得到待比较明文的密文结果；；式中，为多项式复合运算结果，x为多项式的输入密文。

技术总结
本发明公开了一种基于全同态加密的密文同态比较方法和装置，属于密文数据处理技术领域。其中，方法包括根据输入精度和输出精度，确定分量多项式；以及根据所述分量多项式确定待比较明文对应符号函数的近似值。本发明公开的同态比较近似方法在深度消耗和计算复杂性方面具有最优性，可有效减少同态乘法和加法次数，并需要更少的平摊运行时间，更适用于数据量大的应用场景。量大的应用场景。量大的应用场景。


技术研发人员：李晓东 冯夏梦 金鑫 高贺贺 杨舒雅 杨心怡 朱晓鹏
受保护的技术使用者：北京电子科技学院
技术研发日：2023.08.23
技术公布日：2023/9/20