一种基于整数多项式环上的非对称全同态加密方案

孙霓刚 陈宣任 朱浩然

摘  要： 大数据时代下用户数据的隐私安全面临着重大威胁。全同态加密因其满足云计算安全性需求的特性日益受到重视，所以同态加密算法成为保护云端数据的一种有效手段。基于整数多项式环构建了一种非对称的全同态加密方案，其中，包括密钥生成算法、加密算法、解密算法、重加密算法、解密正确性证明以及同态性证明。该方案运行一次KeyGen算法生成一次参数，即可以对批量的明文进行加密运算，也可以对批量的密文进行同态运算，加密效率和同态计算效率高，且该方案的安全性基于近似最大公约数问题。

关键词： 全同态加密; 整数多项式环; 近似最大公约数; 云计算; 同态性; 加密效率

中图分类号： TN915.08?34; TP309.7                 文献标识码： A                  文章编号： 1004?373X（2020）05?0086?06

An asymmetric fully homomorphic encryption scheme based on integer polynomial ring

SUN Nigang， CHEN Xuanren， ZHU Haoran

（School of Information Science & Engineering， Changzhou University， Changzhou 213000， China）

Abstract： Privacy security of user data are facing major threats in the era of big data. Fully homomorphic encryption has drawn more and more attention since it can satisfy the security requirements of cloud computing， thus， the homomorphic encryption algorithm has become an effective method to protect cloud data. An asymmetric fully homomorphic encryption scheme is constructed based on the integer polynomial ring， which contains the key generation algorithm， the encryption algorithm， the decryption algorithm， the re?encryption algorithm， the proof of decryption correctness and the proof of homomorphism. This scheme can encrypt batches of plaintext or perform homomorphic operations on batches of ciphertext by running key generation algorithm once and generating parameters once， thus the encryption efficiency and homomorphic calculation efficiency are high. The security of this scheme is on the basis of the approximate GCD （greatest common divisor）.

Keywords： fully homomorphic encryption; integer polynomial ring; approximate GCD; cloud computing; homomorphic performance; encryption efficiency

0  引  言

随着“大数据时代”的来临，云计算的不断发展，云环境下用户对储存隐私数据的介质产生了怀疑：服务器方面保密机制不够完善，信誉无法保证，对隐私数据的安全构成隐患的问题不能被完全解决。因此，如何在保证用户隐私数据安全的前提下，将其传递到网络服务器端，成为讨论和研究的热门话题。选择一个合适的加密算法对隐私数据进行先解密再上传，最终成为解决这一问题的一个最为便捷、有效的手段。经过不断的研究、分析和实验，全同态加密算法脱颖而出，因其特性成为了最为合适的加密算法。全同态加密是一种可以让任何人对加密后的密文做任意功能的运算，得到的结果解密后，相当于对明文进行了等价运算[1]的算法。在云计算中，有时候需要第三方对数据进行处理，为了确保用户数据的隐私安全，只能给第三方加密后的数据，与此同时，并不能告知第三方私钥的值，这时全同态加密就起到了至关重要的作用。除了云计算方面，全同态加密方案也被应用在其他的许多方面，例如，电子投票、隐私数据处理、加密搜索等。

文献[2]根据RSA公钥密码体制部分运算同态这一特性，提出了隐私全同态的概念，这也是隐私全同态这一概念首次被提出。这个概念提出后，国内外研究人员针对这一问题进行了大量的研究[3?5]。

文献[6]提出了第一个全同态加密方案，该方案分为两部分：构造一个somewhat（部分）同态加密方案，以及利用引用自举电路使之成为全同态加密方案。由于该方案计算的复杂性，在实际布局中是不可行的。在此之后，文献[7]将该方案在理想格上实现了。在构建的新方案中，已经对很多问题进行了显著的优化。然而该方案的运算复杂度依旧很高，在保证安全性的设置下，格的维数[n=]32 768时，公钥的尺寸约为2.3 GB，运用高性能计算机进行运算，密钥的生成时间为2.2 h，加密需要3 min，单次刷新密文[8]需要30 min。

文献[9]提出了一个较为简单的全同态加密方案。该方案是基于整数环上的，而不是理想格上的，然而在将方案构建完成后发现，该方案的公钥尺寸与预期相比太大，以至于该方案无法实现。

文献[10]提出了一个缩短全同态加密方案中公钥尺寸的想法。同年，Stehle和Steinteld在文献[10]提出方案的基础上，进一步缩短了公钥尺寸。同年，Brakerski和Vaikuntanathan提出一个基于LWE困难度问题来构建全同态加密方案。

自隐私全同态概念提出以来，众多学者分别基于理想格、LWE环和整数环等提出了许多不同的方案。这些分别基于不同环上的加密方案，经过不断的研究、分析和改进，用不同的方法让方案从部分同态实现全同态，也不断地使用不同的方法来降低公钥尺寸和提高加密效率。但是上述方案一次都只能对1 bit的明文或密文进行处理。不同于众多学者所研究的理想格、LWE以及整数环等，本文基于整数多项式环构建了一个非对称的全同态加密方案，其中包含了参数的生成、加密算法、解密算法解密正确性和同态性的证明。本方案可以对批量的明文进行加密，也可对批量的密文进行同态运算。在KeyGen阶段，本方案参数的数量级较小，运算复杂度低，且只需生成一次参数，即可实现对批量的明文进行加密处理，降低了运算复杂度，进而提高了加密的效率。

1  数学背景

1.1  近似最大公约数问题

给定一个随机选择的整数集[S={x0，x1，x2，…，xn}]，每一个[xi]都是接近于大素数[p]，[p]是这些整数的近似公因子，寻找这个近似公因子[p]的问题称为近似最大公约数问题（Greatest Common Divisor，GCD）。

1.2  多項式环的定义

[R]为一个环，定义[R[x]={a0+a1x+…+][anxnai∈R}]，其中，[x]是不确定的，[px=a0+a1x+…+][anxn]叫作在[R]上的关于[x]的多项式。

1.3  多项式环上的一些性质和结论

1） [p（x）=a0+a1x+…+anxn，an≠0，ai∈R]，那么[n]叫作多项式[p（x）]的阶。

2） [p（x）=i=0naixi]，[qx=i=0mbixi]分别是[n]阶，[m]阶的两个多项式，定义多项式上的“+”为：

[p（x）+qx=i=0max（n，m）（ai+bi）xi];其中，[ai=0]，[?i>n]，[bi=0]，[?i>m]。

3） [p（x）=i=0naixi]，[qx=i=0mbixi]分别是[n]阶，[m]阶的两个多项式，定义多项式上的（*）为： [px*qx=i=0n+mcixi];其中，[ci=r+s=iar?bs]。

2  非对称的整数多项式环上的全同态加密方案

2.1  参数生成算法（KeyGen）

1） 定义安全参数为[?]。

2） 定义私钥为[Sk]，[Sk]是长度为[?]随机生成的一个质数。

3） 定义[γ]为公钥的比特长度。

4） 定义[ρ]为第一次加密后噪声的比特长度。

5） 定义[di（x）]为一个整数多项式，多项式的系数为[ai]，[di（x）]为密钥生成阶段随机生成的，其中，[（ai）min≥0]，[（ai）max<2γsk]，也就是说，[di（x）]每一项的系数的取值范围为[0，2γsk]。

6） 定义[ri（x）]为一个整数多项式，多项式的系数为[bi]，[ri（x）]为密钥生成阶段随机生成的，其中，[（bi）min>-2ρ]，[（bi）max<2ρ]，也就是说，[ri（x）]的每一项系数的取值范围为[-2ρ，2ρ]。

7） 定义[xi]为一个整数多项式，[xi=sk?di（x）+]

[2ri（x）]。

8） 定义一个集合[xi;xi=sk?di（x）+2ri（x）]，公钥[pk]就是这个集合[xi]的子集，加密时随机地从[xi]中选取一个子集合[S]。

2.2  加密算法（Encrypt）

将明文[m]进行预处理，将明文信息表示成多项式的形式，从而使得明文信息可以编码进入多项式[mp（x）]中。将明文[m]表示成二进制的形式，[m]的二进制数从高位到低位，每一位的位数分别与多项式[mp（x）]的最高次项到最低次项的每一项的阶数相对应，其每一位的值分别代表多项式[mp（x）]的最高次项到最低次项的每一项的系数。加密之前的预处理将明文改写成多项式的形式，这样加密时就可以直接对多项式[mp（x）]进行加密，方便加密过程的进行。[Enc：c（x）=m（x）+2?r（x）+i∈ssk?di（x）+2ri（x）]，其中，[s]是{0，1，2，…}的子集。

2.3  解密算法（Decrypt）

[Dec： m（x）=c（x）modskmod2]

2.4  重加密算法（Recrypt）

定义[rk=z?sk]，重加密之后的密文为[c]，那么重加密算法为：[c（x）≡c（x）modrk]。重加密密文解密正确性证明：根据数学背景中写到的倍数间同余的性质可知，因为[rk=z?sk]，[c（x）≡c（x）modrk]，所以[c（x）≡][c（x）modsk]，也就是说，[c]和[c]关于[sk]是同余的，那么在解密过程中，因为模[sk]的值相等，所以再次模2的值一定相等，所以重加密之后的值，解密之后的结果和原密文相等，证毕。

4  实例证明

为使方案更加具有说服力，在该部分介绍几个实例，通过计算来证明该方案解密的正确性以及同态计算的正确性。任意选取两个数作为明文[m1=6]，[m2=9]，将其表示成二进制的形式[m1=0110]，[m2=1001]，对其进行预处理，将其编码为多项式，表示成多项式的形式[mp1（x）=x2+x]，[mp2（x）=x3+1]。

1） 对[mp1（x）]进行加密，加密过程为：[c1（x）=mp1（x）+2?r1（x）+i∈s1sk?di（x）+2?ri（x）]，其他多项式和私钥[sk]在参数生成算法中根据参数的取值范围随机生成。[sk=813]，[r1（x）=5x2+3x]，[di1（x）=51x2+73x]，[di2（x）=4x+23]，[di3（x）=65x2+x]，[ri1（x）=3x2]，[ri2（x）=5x2+2x]，[ri3（x）=x+2]。将这些多项式代入加密算法中进行计算可得：[c1（x）=94 335x2+63 427x+18 703]。

2） 对[mp2（x）]进行加密，私钥[sk]与加密[mp1（x）]相同，加密过程为：[c2（x）=mp2（x）+2?r2（x）+][j∈s2sk?dj（x）+]

[2?rj（x）]，[r2（x）=3x2+x]，[dj1（x）=72x3+12]，[dj2（x）=31x2+]

[x+7]，[dj3（x）=21x+1]，[rj1（x）=x2+x]，[rj2（x）=][6x+5]，

[rj3（x）=3x2+1]。

将这些多项式代入加密算法中进行计算可得：[c2（x）=58 537x3+25 217x2+17 902x+16 273]。

3） 验证解密的正确性。

上文已经计算出[mp1（x）]加密后得到的[c1（x）]的值，解密算法为：[m（x）=c（x）modskmod2]，所以分别对[c1（x）]每一项的系数进行先模813再模2的计算：94 335mod813mod2=1，63 427mod813mod2=1，18 703mod

813mod2=0，解密后的明文[m′p1（x）=x2+x]与[mp1（x）]相等，[m1]解密正确。对[c2（x）]每一项的系数也进行同样的模运算，58 537mod813mod2=1，25 217mod813mod2=0，17 902mod813mod2=0，16 273mod813mod2=1，解密后的明文[m′p2（x）=x3+1]与[mp2（x）]相等，[m2]解密正确，至此，解密正确性验证完毕，能够正确解密。

4） 验证加法同态性。

[c1（x）+c2（x）=94 335x2+63 427x+18 703+58 537x3+]

[25 217x2+17 902x+16 273 =          58 537x3+119 552x2+]

[81 329x+][34 976]，对其进行解密运算，58 537mod 813mod2=1，119 552mod813mod2=1，81 329mod 813mod2=1，34 976mod813mod2=1，解密后的结果为：[x3+x2+x+1]。[mp1（x）+mp2（x）=x3+x2+x+1]，解密后的结果与其相等，所以加密同态性验证完毕。

5） 验证乘法同态性。

[c1（x）?c2（x）=（94 335x2+63 427x+18 703）?（58 537x3+]

[25 217x2+17 902x+16 273）         =         5 522 087 895x5+][6 091 671 994x4  +   4 383 041 341x3   +   3 142 217 160x2+]

[1 366 968 677x+304 353 919]，對每一项的系数进行模813再模2的运算进行解密，5 522 087 895mod813mod2=1，6 091 671 994mod813mod2=1，4 383 041 340mod813 mod2=0，3 142 217 160mod813mod2=1，1 366 968 677mod 813mod2=1，304 353 919mod813mod2=0，解密后的结果为：[x5+x4+x2+x]，[mp1（x）?mp2（x）=x5+x4+x2+x]，[c1（x）?c2（x）]解密后的结果与其相等，所以乘法同态性验证完毕，至此，同态性验证完毕。

5  结  语

本文构建了一个基于整数多项式环上的非对称全同态加密方案，该方案是一个可以对明文和密文进行批处理的全同态加密方案。在该方案的重加密算法中无需进行同态加密，这与其他的全同态加密方案相比是一个显著的优势。因为在重加密算法中，同态解密是一个复杂度相当高的算法，因为本文构建的方案无需进行同态解密，所以在很大程度上降低了运算复杂度，提高了效率。

参考文献

[1] 陈智罡，王箭，宋新霞.全同态加密研究[J].计算机应用研究，2014，31（6）：1624?1630.

[2] RIVEST R L， ADLEMAN L M， DERTOUZOS M L. On data banks and privacy homomorphisms [J]. Foundations of secure computation， 1978， 7（1）： 169?179.

[3] DOMINGO?FERRER J. A provably secure additive and multiplicative privacy homomorphism [C]// Proceedings of the Fifth International Conference on Information Security. Berlin： Springer?Verlag， 2002： 471?483.

[4] BRICKELL E F， YACOBI Y. On privacy homomorphisms （Extended abstract） [C]// Workshop on Advances in Cryptology?EuroCrypt. Amsterdam， The Netherlands： Springer?Verlag， 1987： 117?125.

[5] GENTRY， CRAIG. Fully homomorphic encryption using ideal lattices [C]// Proceedings of the Annual ACM Symposium on Theory of Computing. Bethesda， MD： ACM， 2009： 169?178.

[6] PFITZMANN B， WAIDNER M. Attacks on protocols for server?aided computation [C]// Workshop on the Theory and Application of Cryptographic Techniques. Berlin， Germany： Springer?Verlag， 1993： 153?162.

[7] GENTRY C， HALEVI S. Implementing Gentrys fully?homomorphic encryption scheme [C]// Proceedings of the 30th Annual International Conference on Theory and Applications of Cryptographic Techniques： Advances in Cryptology. Berlin： Springer?Verlag， 2011： 129?148.

[8] 罗炳聪，柳青，马远，等.具有较短公钥的批处理整数上的全同态加密方案[J].计算机应用研究，2014，31（4）：1180?1184.

[9] DIJK M V， GENTRY C， HALEVI S， et al. Fully homomorphic encryption over the integers [C]// Advances in Cryptology?EUROCRYPT. Berlin： Springer， 2010： 24?43.

[10] CORON JEAN?S?BASTIEN， MANDAL AVRADIP， NACCACHE DAVID， et al. Fully homomorphic encryption over the integers with shorter public keys [C]// Conference on Advances in Cryptology. Santa Barbara， CA， USA： Springer?Verlag， 2011： 487?504.