基于二元截断多项式环的无噪音全同态公钥加密方法

摘要

本发明提出了一种基于二元截断多项式环的无噪音全同态公钥加密方法，用于解决现有技术中存在的密钥和密文过长且密文同态计算效率低的技术问题。实现步骤为：用户设置参数，获取解密私钥、加密公钥和密文同态计算公钥，并构造二元截断多项式环，通过采用加密公钥对明文进行概率加密，得到属于二元截断多项式环的密文，通过采用解密私钥对密文进行解密，得到密文对应的明文；云服务器采用密文同态计算公钥，对密文进行同态计算，得到属于二元截断多项式环的同态密文；用户采用解密私钥，对同态密文进行解密，得到相应明文进行相同计算的结果。本发明的密文和秘钥长度均为常数级，同态计算效率高。

说明书

技术领域

本发明涉及一种全同态加密方法，具体涉及一种基于二元截断多项式环的无噪音全同态公钥加密方法，可应用于云计算、大数据等数据委托计算服务，提供重要数据的存储、访问、统计、挖掘等全程密态隐私保护。

背景技术

随着数字信息的爆炸式增长和个人与组织对这些信息的依赖性不断增强，大规模数据库逐渐成为整个信息系统的中心，数据成为最重要的资产。对于大规模数据的使用，数据库往往以委托计算的方式外包给第三方，但是存在信息泄露的风险，这需要对数据库进行加密以保护数据的隐私性。然而，一般性的数据加密操作会对明文的数据结构进行本质上的破坏，使得密态数据丧失了信息再处理功能。因此，需要一种能在加密数据上进行有效计算的加密方法。

全同态加密作为一种加密形式，它允许用户对密文进行特定的代数运算得到仍是加密的结果，将其解密与对应的明文进行相同代数运算所得到的结果一样。换言之，这项技术令用户可以在已加密的数据上进行任意多次的加法和乘法操作，从而得出相应明文的计算结果所对应的密文，而在整个处理过程中无需对数据进行解密。其意义在于，真正从根本上解决了数据委托计算服务中数据的隐私保护和密态数据的信息再处理之间相互冲突的技术瓶颈问题。一般来说，一种全同态加密方法主要包含参数设置、密钥获取、加密、解密和密文同态计算这五个步骤。

目前出现的同态加密方案可分为三种类型：部分同态加密、浅同态加密和全同态加密。部分同态加密只能够实现某一种代数运算(加或乘)；浅同态加密虽能同时实现密文的加法运算和乘法运算，但是运算次数有限，这样使得部分同态加密和浅同态加密的计算功能受限，无法满足实际需求。和浅同态加密相比，全同态加密不受密文运算次数的限制，同时根据在密文中是否引入噪音可分为有噪音全同态加密和无噪音全同态加密。值得注意的是，现有的可证明安全的全同态公钥加密方法在密文中均引入了噪音，因此，在密文同态计算阶段，随着电路层数增加，同态计算的密文中的噪音会逐渐积累，而当噪声累积到超过门限值时，就需繁琐的步骤对密文进行更新，这样使得密文同态计算过程效率低，同时还存在着因密文和密钥过长导致浪费存储空间和通信带宽的技术问题。例如，Zhang P等人在会议《International Conference on Cloud Computing&Intelligence Systems》上发表了题目为“An accelerated fully homomorphic encryption scheme over the integers”的论文(2016:419-423)，公开了一种改进的全同态公钥加密方法，该方法的实现过程是先构造一种浅同态公钥加密方法，并利用公钥压缩技术和中国剩余定理来降低公钥尺寸和密文尺寸；而后，再利用压缩解密电路技术将这个浅同态公钥加密方法转换为一种全同态公钥加密方法，即在密文同态计算的过程中，当同态计算的密文中的噪声累积到门限值时，利用压缩和自举技术对密文进行更新，从而达到支持任意次同态计算的目的。该全同态公钥方法的缺点在于，虽然利用公钥压缩技术和中国剩余定理降低了密钥和密文的尺寸，但其尺寸仍旧过大，极大的浪费了存储空间及通信带宽，同时，该方法在密文同态计算过程中需要对密文进行更新，步骤繁琐、效率低。

发明内容

本发明的目的在于克服上述现有技术存在的缺陷，提出了一种基于二元截断多项式环的无噪音全同态公钥加密方法，用于解决现有技术中存在的密钥和密文过长且密文同态计算效率低的技术问题。

为实现上述目的，本发明采取的技术方案包括如下步骤：

(1)参数设置：用户根据自身安全需求设置安全参数k，并定义明文空间M＝{0,1}^k-1为所有k-1比特长整数的集合，其中，k≥1024；

(2)用户获取解密私钥sk、加密公钥pk_E和密文同态计算公钥pk_H，并构造二元截断多项式环实现步骤为：

(2.1)用户在安全参数k的控制下，随机生成两个k比特长的大素数p和q，并计算RSA模数N，N＝pq，再分别构造模p意义下的剩余类环模q意义下的剩余类环和模N意义下的剩余类环

(2.2)用户在剩余类环中均匀且随机选取两个整数a和b，并与大素数p一起构成解密私钥sk＝(a,b,p)；

(2.3)用户在剩余类环中均匀且随机选取17个整数a_i、b_i和a_ij，i＝1,2,3,4，i,j＝0,1,2，并由这些整数构造三个二元多项式f₁(x,y)、f₂(x,y)和f₃(x,y)：

f₁(x,y)＝x³+a₁xy+a₂x+a₃y+a₄，

f₂(x,y)＝y³+b₁xy+b₂x+b₃y+b₄，

(2.4)用户采用三个二元多项式f₁(x,y)、f₂(x,y)和f₃(x,y)，分别计算三个含有公共根(a,b)的二元多项式g₁(x,y)、g₂(x,y)和g₃(x,y)：

g₁(x,y)≡f₁(x,y)-f₁(a,b)≡x³+a₁xy+a₂x+a₃y+a₄′(mod>

g₂(x,y)≡f₂(x,y)-f₂(a,b)≡y³+b₁xy+b₂x+b₃y+b₄′(mod>

其中，a₄′、b₄′和a₀′₀分别为二元多项式g₁(x,y)、g₂(x,y)和g₃(x,y)的常数项；

(2.5)用户在剩余类环中均匀且随机选取17个整数c_i、d_i和c_ij，i＝1,2,3,4，i,j＝0,1,2，并由这些整数构造三个二元多项式h₁(x,y)、h₂(x,y)和h₃(x,y)：

h₁(x,y)＝x³+c₁xy+c₂x+c₃y+c₄，

h₂(x,y)＝y³+d₁xy+d₂x+d₃y+d₄，

(2.6)用户利用中国剩余定理，获取三个定义在剩余类环上且含有公共根(a,b)的二元多项式F₁(x,y)、F₂(x,y)和F₃(x,y)：

F₁(x,y)＝x³+e₁xy+e₂x+e₃y+e₄，

F₂(x,y)＝y³+z₁xy+z₂x+z₃y+z₄，

其中，e_i、z_i和e_ij分别为二元多项式F₁(x,y)、F₂(x,y)和F₃(x,y)的系数，且i＝1,2,3,4，i,j＝0,1,2；

(2.7)由二元多项式F₁(x,y)、F₂(x,y)、F₃(x,y)和RSA模数N，构造加密公钥pk_E＝(N,F₁(x,y),F₂(x,y),F₃(x,y))，同时由二元多项式F₁(x,y)、F₂(x,y)和RSA模数N，构造密文同态计算公钥pk_H＝(N,F₁(x,y),F₂(x,y))；

(2.8)用户采用二元多项式F₁(x,y)和F₂(x,y)，构造元素为关于变量x,y次数不超过2、系数属于剩余类环最多含有9项的二元多项式的二元截断多项式环其中，模N的剩余类环上的二元多项式环为

(3)用户对明文进行概率加密，实现步骤为：

(3.1)用户根据需求选择t条明文M_t∈M，并均匀且随机选取t个概率加密参数其中，t≥2；

(3.2)用户采用概率加密参数r_t和加密公钥pk_E，分别对t条明文M_t进行概率加密：用户计算并采用二元多项式F₁(x,y)、F₂(x,y)和RSA模数N对计算结果取模，得到t个属于二元截断多项式环的二元多项式C_t(x,y)，并将其作为t条明文M_t对应的密文；

(4)用户对密文C_t(x,y)进行解密：用户采用解密私钥sk，对各明文M_t对应的密文C_t(x,y)分别进行解密，得到t条密文C_t(x,y)对应的不同明文M_t；

(5)云服务器对密文进行同态计算：

(5.1)云服务器根据用户需求，从t条密文C_t(x,y)中选择明文M₁、M₂、M₁′和M₂′对应的密文C₁(x,y)、C₂(x,y)、C₁′(x,y)和C₂′(x,y)，其中，明文M₁、M₂、M₁′和M₂′相同或不同；

(5.2)云服务器采用密文同态计算公钥pk_H，对密文C₁(x,y)和C₂(x,y)进行同态加法计算：云服务器计算C₁(x,y)+C₂(x,y)，并采用二元多项式F₁(x,y)、F₂(x,y)和RSA模数N对计算结果取模，得到属于二元截断多项式环的二元多项式C₊(x,y)，并将其作为密文C₁(x,y)和C₂(x,y)的加法同态密文；

(5.3)云服务器采用密文同态计算公钥pk_H，对密文C₁′(x,y)和C₂′(x,y)进行同态加法计算：云服务器计算C₁′(x,y)C₂′(x,y)，并采用二元多项式F₁(x,y)、F₂(x,y)和RSA模数N对计算结果取模，得到属于二元截断多项式环的二元多项式C_×(x,y)，并将其作为密文C₁′(x,y)和C₂′(x,y)的乘法同态密文；

(6)用户对同态密文进行解密：

(6.1)用户采用解密私钥sk，对密文C₁(x,y)和C₂(x,y)对应的加法同态密文C₊(x,y)进行解密，得到加法同态密文C₊(x,y)对应的明文M₊＝M₁+M₂，其中，解密公式为：

M₊≡C₊(a,b)(mod>

(6.2)用户采用解密私钥sk，对密文C₁′(x,y)和C₂′(x,y)对应的乘法同态密文C_×(x,y)进行解密，得到乘法同态密文C_×(x,y)对应的明文M_×＝M₁′M₂′，其中，解密公式为：

M_×≡C_×(a,b)(mod>

本发明与现有技术相比，具有以下优点：

1、本发明由于在加密和密文同态计算过程中，引入二元多项式对计算结果进行取模，使得多项式在乘法计算过程中项数不会增加，从而控制了密文的增长，所有密文及密钥长度均为常数级，与现有技术相比，极大的降低了密文及密钥所需的存储空间和通信带宽。

2、本发明由于在加密过程中，使用含有公共根的三个多项式对明文进行概率加密，而未引入噪音，从而避免了现有的有噪音全同态加密方法在密文同态计算中繁琐的密文刷新过程，与现有技术相比，有效的提高了密文同态计算过程的效率。

附图说明

附图1为本发明的实现流程图。

具体实施方式

以下结合附图和具体实施例，对本发明进行进一步详细说明。

参照附图1，基于二元截断多项式环的无噪音全同态公钥加密方法，实现步骤为：

步骤1)参数设置：用户根据自身安全需求设置安全参数k，并定义明文空间M＝{0,1}^k-1为所有k-1比特长整数的集合，其中，k＝1024；

步骤2)用户获取解密私钥sk、加密公钥pk_E和密文同态计算公钥pk_H，并构造二元截断多项式环实现步骤为：

步骤2.1)用户在安全参数k的控制下，随机生成两个k比特长的大素数p和q，并计算RSA模数N，N＝pq，再分别构造模p意义下的剩余类环模q意义下的剩余类环和模N意义下的剩余类环

步骤2.2)用户在剩余类环中均匀且随机选取两个整数a和b，并与大素数p一起构成解密私钥sk＝(a,b,p)；

步骤2.3)用户在剩余类环中均匀且随机选取17个整数a_i、b_i和a_ij，i＝1,2,3,4，i,j＝0,1,2，并由这些整数构造三个二元多项式f₁(x,y)、f₂(x,y)和f₃(x,y)：

f₁(x,y)＝x³+a₁xy+a₂x+a₃y+a₄，

f₂(x,y)＝y³+b₁xy+b₂x+b₃y+b₄，

步骤2.4)用户采用三个二元多项式f₁(x,y)、f₂(x,y)和f₃(x,y)，分别计算三个含有公共根(a,b)的二元多项式g₁(x,y)、g₂(x,y)和g₃(x,y)：

g₁(x,y)≡f₁(x,y)-f₁(a,b)≡x3+a₁xy+a₂x+a₃y+a₄′(mod>

g₂(x,y)≡f₂(x,y)-f₂(a,b)≡y3+b₁xy+b₂x+b₃y+b₄′(mod>

其中，a₄′、b₄′和a₀′₀分别为二元多项式g₁(x,y)、g₂(x,y)和g₃(x,y)的常数项；

本步骤所述二元多项式g₁(x,y)、g₂(x,y)和g₃(x,y)含有公共根(a,b)，其原因在于：用户将整数a和整数b带入二元多项式g₁(x,y)、g₂(x,y)和g₃(x,y)中，计算g₁(a,b)≡f₁(a,b)-f₁(a,b)≡0(mod>2(a,b)≡f₂(a,b)-f₂(a,b)≡0(mod>3(a,b)≡f₃(a,b)-f₃(a,b)≡0(mod>1(x,y)、g₂(x,y)和g₃(x,y)分别满足g₁(a,b)≡0(mod>2(a,b)≡0(mod>3(a,b)≡0(mod>1(x,y)、g₂(x,y)和g₃(x,y)含有公共根(a,b)。

步骤2.5)用户在剩余类环中均匀且随机选取17个整数c_i、d_i和c_ij，i＝1,2,3,4，i,j＝0,1,2，并由这些整数构造三个二元多项式h₁(x,y)、h₂(x,y)和h₃(x,y)：

h₁(x,y)＝x³+c₁xy+c₂x+c₃y+c₄，

h₂(x,y)＝y³+d₁xy+d₂x+d₃y+d₄，

步骤2.6)用户利用中国剩余定理，获取三个定义在剩余类环上且含有公共根(a,b)的二元多项式F₁(x,y)、F₂(x,y)和F₃(x,y)：

F₁(x,y)＝x³+e₁xy+e₂x+e₃y+e₄，

F₂(x,y)＝y³+z₁xy+z₂x+z₃y+z₄，

其中，e_i、z_i和e_ij分别为二元多项式F₁(x,y)、F₂(x,y)和F₃(x,y)的系数，且i＝1,2,3,4，i,j＝0,1,2，其计算公式分别为：

i＝1,2,3时，e_i≡a_i(mod>i≡c_i(mod>4≡a₄′(mod>4≡c₄(mod>

i＝1,2,3时，z_i≡b_i(mod>i≡d_i(mod>4≡b₄′(mod>4≡d₄(mod>

i,j＝0,1,2，且当i,j不同时为0时，e_ij≡a_ij(mod>ij≡c_ij(mod>

e₀₀≡a₀′₀(mod>00≡c₀₀(mod>

本步骤中利用中国剩余定理对二元多项式F₁(x,y)、F₂(x,y)和F₃(x,y)的系数按如上方式进行计算，实质上是要求所获取的二元多项式F₁(x,y)、F₂(x,y)和F₃(x,y)分别满足：

F₁(x,y)≡g₁(x,y)(mod>1(x,y)≡h₁(x,y)(modq)，

F₁(x,y)≡g₁(x,y)(mod>1(x,y)≡h₁(x,y)(modq)，

F₁(x,y)≡g₁(x,y)(mod>1(x,y)≡h₁(x,y)(modq)，

同时，由步骤(2.4)中二元多项式g₁(x,y)、g₂(x,y)和g₃(x,y)分别满足g₁(a,b)≡0(mod>2(a,b)≡0(mod>3(a,b)≡0(mod>1(x,y)、F₂(x,y)和F₃(x,y)将分别满足F₁(a,b)≡0(mod>2(a,b)≡0(mod>3(a,b)≡0(mod>1(x,y)、F₂(x,y)和F₃(x,y)含有公共根(a,b)。

步骤2.7)由二元多项式F₁(x,y)、F₂(x,y)、F₃(x,y)和RSA模数N，构造加密公钥pk_E＝(N,F₁(x,y),F₂(x,y),F₃(x,y))，同时由二元多项式F₁(x,y)、F₂(x,y)和RSA模数N，构造密文同态计算公钥pk_H＝(N,F₁(x,y),F₂(x,y))；

步骤2.8)用户采用二元多项式F₁(x,y)和F₂(x,y)，构造元素为关于变量x,y次数不超过2、系数属于剩余类环最多含有9项的二元多项式的二元截断多项式环其中，模N的剩余类环上的二元多项式环为

步骤3)用户对明文进行概率加密，实现步骤为：

步骤3.1)用户根据需求选择t条明文M_t∈M，并均匀且随机选取t个概率加密参数其中，t≥2；

步骤3.2)用户采用概率加密参数r_t和加密公钥pk_E，分别对t条明文M_t进行概率加密：用户计算并采用二元多项式F₁(x,y)、F₂(x,y)和RSA模数N对计算结果取模，得到t个属于二元截断多项式环的二元多项式C_t(x,y)，并将其作为t条明文M_t对应的密文；

步骤4)用户对密文C_t(x,y)进行解密：用户采用解密私钥sk，对各明文M_t对应的密文C_t(x,y)分别进行解密，得到t条密文C_t(x,y)对应的不同明文M_t，其中，解密公式为：

M_t≡C_t(x,y)(mod>

本发明能够正确解密的原理在于：在加密过程中，用户计算并采用二元多项式F₁(x,y)、F₂(x,y)和RSA模数N对的计算结果进行取模，得到属于二元截断多项式环的二元多项式C_t(x,y)，并将其作为明文M_t对应的密文，因此存在三个二元多项式E₁(x,y)、E₂(x,y)和E₃(x,y)，使得如下等式成立：

同时，由步骤(2.6)可知，二元多项式F₁(x,y)、F₂(x,y)和F₃(x,y)分别满足F₁(a,b)≡0(mod>2(a,b)≡0(mod>3(a,b)≡0(mod>1(a,b)E₁(a,b)≡0(modp)、F₂(a,b)E₂(a,b)≡0(mod>由步骤(2.1)中N＝pq可知，N≡0(mod p)，进而有NF₃(a,b)≡0(mod>t(x,y)中，计算最终可正确解密得到密文C_t(x,y)对应的明文M_t。

步骤5)云服务器对密文进行同态计算：

步骤5.1)云服务器根据用户需求，从t条密文C_t(x,y)中选择明文M₁、M₂、M₁′和M₂′对应的密文C₁(x,y)、C₂(x,y)、C₁′(x,y)和C₂′(x,y)，其中，明文M₁、M₂、M₁′和M₂′相同或不同；

步骤5.2)云服务器采用密文同态计算公钥pk_H，对密文C₁(x,y)和C₂(x,y)进行同态加法计算：云服务器计算C₁(x,y)+C₂(x,y)，并采用二元多项式F₁(x,y)、F₂(x,y)和RSA模数N对计算结果取模，得到属于二元截断多项式环的二元多项式C₊(x,y)，并将其作为密文C₁(x,y)和C₂(x,y)的加法同态密文；

步骤5.3)云服务器采用密文同态计算公钥pk_H，对密文C₁′(x,y)和C₂′(x,y)进行同态加法计算：云服务器计算C₁′(x,y)C₂′(x,y)，并采用二元多项式F₁(x,y)、F₂(x,y)和RSA模数N对计算结果取模，得到属于二元截断多项式环的二元多项式C_×(x,y)，并将其作为密文C₁′(x,y)和C₂′(x,y)的乘法同态密文；

在加密、密文同态加法计算和密文同态乘法计算过程中，用户均采用二元多项式F₁(x,y)＝x³+e₁xy+e₂x+e₃y+e₄、F₂(x,y)＝y³+z₁xy+z₂x+z₃y+z₄和RSA模数N分别对C₁(x,y)+C₂(x,y)和C₁′(x,y)C₂′(x,y)的计算结果进行取模，也就是说，碰到x³，将x³替换为-(e₁xy+e₂x+e₃y+e₄)，碰到y³，将y³替换为-(z₁xy+z₂x+z₃y+z₄)，而后采用RSA模数N对所有的系数取模，最终可分别得到属于二元截断多项式环的关于变量x,y次数均不超过2、系数属于剩余类环最多含有9项的二元多项式C_t(x,y)、C₊(x,y)和C_×(x,y)，并将其分别作为明文M_t的密文、密文C₁(x,y)和C₂(x,y)的加法同态密文和密文C₁′(x,y)和C₂′(x,y)的乘法同态密文，由此可知所有密文的长度均为常数级。

步骤6)用户对同态密文进行解密：

步骤6.1)用户采用解密私钥sk，对密文C₁(x,y)和C₂(x,y)对应的加法同态密文C₊(x,y)进行解密，得到加法同态密文C₊(x,y)对应的明文M₊＝M₁+M₂，其中，解密公式为：

M₊≡C₊(a,b)(mod>

本步骤中，用户采用解密私钥sk对加法同态密文C₊(x,y)进行解密，最终正确解密，得到加法同态密文C₊(x,y)对应的明文M₊＝M₁+M₂，其推导过程为：

M₊≡C₊(a,b)(mod>1(a,b)+C₂(a,b)(mod>1(x,y),F₂(x,y)))(mod>1+M₂(mod>1+M₂。

步骤6.2)用户采用解密私钥sk，对密文C₁′(x,y)和C₂′(x,y)对应的乘法同态密文C_×(x,y)进行解密，得到乘法同态密文C_×(x,y)对应的明文M_×＝M₁′M₂′，其中，解密公式为：

M_×≡C_×(a,b)(mod>

本步骤中，用户采用解密私钥sk对乘法同态密文C_×(x,y)进行解密，最终正确解密，得到乘法同态密文C_×(x,y)对应的明文M_×＝M₁′M₂′，其推导过程为：

M_×≡C_×(a,b)(mod>1′(a,b)C₂′(a,b)(mod>1(x,y),F₂(x,y)))(mod>1′M₂′(mod>1′M₂′。

以上描述仅是本发明的一个具体实例，显然对于本领域的专业人士来说，在了解了本发明内容和原理后，都不可能在背离本发明原理、结构的情况下，进行形式和细节上的各种修正和改变，但是这些基于本发明思想修正和改变仍在本发明的权利要求保护范围之内。