全同态加密中重加密深度优化方法

摘要

本发明公开了一种全同态加密中的重加密深度优化方法，通过在该加密技术中全同态评估处理部分增加深度阈值计算与判断以及重加密深度优化及处理步骤来提高效率，实现全同态加密方法的实用化。首先，计算出允许的深度阈值；其次，对给定的待评估函数进行分解，使得分解后的子函数的阶数均小于阈值；最后，利用加法和乘法增强电路将子函数连接起来进行运算；如此便大大降低了重加密的次数，实现了重加密深度优化。本发明的方法不仅在复杂度上远小于现有的全同态重加密方法，同时基于近似最大公约数问题和稀疏子集和等困难问题，其安全性也得到有效保证。

说明书

技术领域

本发明提出了一种全同态加密中的重加密深度优化方法，属于信息安全技术领域。 

背景技术

全同态加密是指对加密后的密文进行各种函数操作等同于对相应明文进行相应操作；也就是说，函数操作后的密文经过解密之后，得到的结果是相应操作直接作用于明文上的效果。全同态加密技术在云计算系统中具有非常重要的应用价值。通过全同态加密，用户可以放心地把自己的数据加密后存放到云存储中心，而后续每次要调取或者查询自己的数据，均可以对云存储中心中的加密数据进行相应处理，返回并解密后得到的就是所需的相应处理后的数据，这既保证了用户数据的安全，又能充分利用云计算存储的可靠与便利。 

全同态加密技术最早可以溯源到1978年李维斯特等人提出的RSA算法，他们认为RSA算法具有乘法同态的功能，也就是说对密文做乘法处理等价于对解密后的明文做相应的处理，但是这不适用于带有加乘等复杂运算的函数处理，而我们称能实现对任意函数处理具有同态特征的加密技术为全同态加密技术。 

在随后的几十年里，全同态加密技术的研究没有获得大的进展。直到2009年，IBM公司的金特里博士首次从数学上提出了全同态加密的可行方法。他提出了基于理想格的加密方案，可以实现加法和乘法同态，同时鉴于噪声随着加密次数的不断增大，为了可以执行无限次同态操作，也就是可以对任意函数电路进行全同态操作，他引入了重加密的概念，也就是对于密文重加密得到对应明文的新鲜密文，从而使噪声大大减小，以便可以进行后续的操作，从而从理论上实现了全同态加密的思想。2010年8月，戴伊克和金特里等人提出了整数上的全同态加密方案，不再使用之前的理想格加密思想，而采用整数模运算，概念上更简单，更易于实现。但是整数上的全同态加密方案为了实现全同态在每次加或乘之前都进行一次重加密以减小噪声，大大增加了运算复杂度。 

发明内容

发明目的：由于现有的全同态加密方法都极其复杂，难以应用实践，如何降低全同态加密方法的复杂度决定了这种方法能否应用。我们提出的全同态加密技术中的重加密 优化方法，通过深度阈值划分而进行不同处理，降低重加密步骤的复杂度，提高整个全同态加密技术的效率及实用性。 

技术方案：为达到上述发明目的，本发明提供了一种全同态加密中的重加密深度优化方法，该方法包括如下步骤： 

在全同态评估步骤中建立重加密深度优化机制，即建立深度阈值计算与判断步骤201和重加密深度优化及处理202步骤； 

深度阈值计算与判断步骤201实现深度阈值的计算，并将输入的评估函数与这个阈值进行比较来确定是否需要进行深度优化； 

在重加密深度优化及处理202步骤中，将输入的评估函数分解为阶数在深度阈值内的子函数，再用加法和乘法增强电路连接各子函数，降低重加密的复杂度。 

优选的，深度阈值计算与判断步骤中的深度阈值计算方法如下： 

步骤201a：先定义好允许电路；令C是一个t个输入的布尔电路，令C⁺是对应的证书电路；令f(x₁，…，x_t)是C⁺计算的多元多项式，令d是该多项式的深度，ρ′是加密时使用的干扰量的长度，η是私钥的长度，如果电路C对应的函数表达式f满足关系式 那么C属于允许电路；由此可以得出能够处理的函数的阶数如下： 

$d\le \frac{\eta -4-\log \left|\overrightarrow{f}\right|}{{\rho }^{\prime }+2}$

步骤201b：为了综合考虑密文的长度和重加密的次数，设定深度阈值

优选的，重加密深度优化及处理202步骤将评估函数分解为阶数小于阈值的子函数；针对评估函数，首先通过泰勒级数展开方法将该评估函数展开为幂函数的表达形式， 

如果幂函数的最高阶小于阈值，那么该函数直接可以进行后续的全同态评估操作； 

如果幂函数的最高阶大于阈值，那么分解幂函数为若干个阶数在阈值范围内的子函数，然后，将子函数用加法和乘法增强电路连接起来，再进行后续的全同态评估操作。 

有益效果： 

本发明所提出的全同态加密中的重加密深度优化方法能有效降低全同态加密的重加密的复杂度，提高全同态加密技术的效率和实用性。 

附图说明

图1为本发明全同态加密中重加密深度优化方法的原理框图； 

图2为例子函数f分解后的子函数连接图。 

具体实施方式

下面结合附图和具体实施例，进一步阐明本发明，应理解这些实施例仅用于说明本发明而不用于限制本发明的范围。 

全同态加密技术是指一种对密文进行运算等价于对相应解密后的明文进行相应运算的一种加密技术，其分为加密、评估处理和解密部分。 

在图1所示的原理框图中，本发明提出的全同态加密中的重加密深度优化方法在全同态评估步骤中建立重加密深度优化机制，建立深度阈值计算与判断和重加密深度优化及处理步骤。深度阈值计算与判断步骤实现深度阈值的计算，并将输入的评估函数与这个深度阈值进行比较来确定是否需要进行深度优化；在重加密深度优化及处理步骤中，将输入的评估函数分解为阶数在深度阈值范围内的子函数，再用加法和乘法增强电路连接各子函数，从而降低全同态方法的复杂度。 

深度阈值计算与判断步骤中的阈值计算如下： 

(1)先定义允许电路；令C是一个t输入的布尔电路，令C⁺是对应的整数电路；令f(x₁，…，x_t)是C⁺计算的多元多项式，令d是该多项式的深度，ρ′是加密时使用的干扰量的长度，η是私钥的长度，如果电路C对应的函数多项式满足关系式那么C属于允许电路；由此可以计算出可以处理的函数的阶数如下： 

$d\le \frac{\eta -4-\log \left|\overrightarrow{f}\right|}{{\rho }^{\prime }+2}$

(2)由于远小于η，所以我们选定深度阈值为这样的选定是为了取更小些的合理深度阈值，为了确保噪声在可控范围内，同时也从某种程度上降低了数据的传输量。 

而重加密深度优化及处理步骤将评估函数分解为阶数在阈值内的子函数；针对评估 函数，首先通过泰勒级数展开为幂函数的表达形式，如果幂函数的最高阶小于阈值，那么该函数直接可以进行全同态操作，如果幂函数的最高阶大于阈值，那么将幂函数中在阈值阶数范围内的函数项分离出来，作为子函数1，剩余函数再除以一个以阈值为阶数的多项式(此多项式函数作为子函数2)，剩余部分若满足阈值阶数，即可作为最后一个子函数3，若剩余部分仍然高于阈值阶数，则如此类推分解下去，即可得到最终的子函数连接表达式。 

图2为一个例子函数f分解后的子函数连接图。举例假设d′＝5，而函数f经过泰勒级数展开后得到f＝x¹¹+3x¹⁰+x⁸+2x⁷+x⁶+4x⁴+x³+x²。令f₁＝4x⁴+x³+x²，则f-f₁＝x¹¹+3x¹⁰+x⁸+2x⁷+x⁶＝x⁴(x⁷+3x⁶+x⁴+2x³+x²)。 

接着，令f₂＝x⁴f₃＝x⁴+2x³+x²，则(f-f₁)/f₂f₃＝x⁷+3x⁶＝x⁴(x³+3x²)＝f₂(x³+3x²)，而f₄＝x³+3x²。所以，评估函数f可以分解成f₂(f₂*f₄+f₃)+f₁的组合。 

上述函数f经过分解后，将得到的子函数之间的加法和乘法运算由对应的加法增强电路和乘法增强电路替换连接，f₂和f₄首先经过乘法增强电路进行组合，得到的结果再与f₃进行加法增强电路组合；依次处理，都得到评估函数f的最终输出。 

具体的重加密深度优化及处理步骤又细分为以下子步骤： 

第一步：根据给定的操作函数f，通过泰勒级数展开成幂函数的形式，再将其分解成若干个子函数相加和相乘的形式，使得每个子函数的阶数小于阈值d′。 

第二步：对输入的密文根据运算函数f执行相应的运算，运算完f后得到密文(c，z)，c是经过一系列运算后得到的大噪声的密文，z是向量，z＝c·y，y为附加的公钥，满足y₁，y₂，...，y_n∈[0，2)。并且存在稀疏子集S，使得{s_i}为附加私钥，s＝<s₁，s₂，......>是0或1的向量，这里的p是选定的大素数私钥。 

第三步：对第二步得到运算结果密文作为新的输入，首先，为了降低噪声必须进行重加密。输入的密文为(c，z)，因为明文空间是{0，1}，所以加密一定是对密文按位来加密。重加密的过程就是解密的过程，但是对象是对加密的密文以及加密的私钥进行。所以有c′＝Enc(Lsb(c))，得到的新的密文c′是一个整数。另外私钥{s}是0，1的向量，对私钥的每一位的加密记为sk′＝<Enc(s₁)，Enc(s₂)，......>＝<s₁′，s₂′，......>，得到的{s′}也是整数。然后运行∑s_i*z_i，把每一个z_i的二进制表示写成矩阵的一行，这样就得到一个矩阵： 

a_1，0  ·  a_1，-1  ……  a_1，-(n-1)  a_1，-n

a_2，0  ·  a_2，-1  ……  a_2，-(n-1)  a_2，-n

a_3，0  ·  a_3，-1  ……  a_3，-(n-1)  a_3，-n

                 ………… 

a_t，0  ·  a_t，-1  ……  a_t，-(n-1)  a_t，-n

然后用{s′}的第i项乘以上面矩阵的第i行的每一位，得到一个整数矩阵。 

第四步：对上述矩阵每一列求汉明重量，利用对称多项式算法求和，最后得到b₀和b_-1，计算b＝b₀+b_-1，b就是对应的Lsb(「Σs_i*z_i」)。 

第五步：根据上面已经得到的c′＝Enc(Lsb(c))，最终得到对密文c的重加密结果为：新密文c^*＝c′+b，c^*是c的重生，噪声比原来大大降低了，变成了新鲜密文。 

第六步：然后将c^*进行相应的门电路运算，例如加或乘，输出得到的结果。 

第七步：根据第六步的输出结果，接下来有两种情况；第一种：此结果为最终结果，那么再进行一次重加密后，将密文还给用户，用户解密后得到正确的运算结果。第二种：此结果不是最终结果，那么继续第三步的运算。 

最终实现了重加密深度优化的全同态加密方法，在保证安全性的同时，提高了方法的效率并有效降低了复杂度。