基于中国剩余定理的公钥加密方案同态性

摘要：针对现有（全）同态加密方案的整体性能不能达到实用要求的问题，为获得新的性能更好的同态加密思路，对基于中国剩余定理（CRT）的快速公钥加密方案的同态性进行了研究。考察了基于原方案构造加法和乘法同态操作的可能性，指出基于原方案不适于构造加法同态操作和乘法同态操作，具体说明是什么问题并分析了原方案在安全性和效率方面存在的几个问题。。提出了一个基于原方案的说明是什么样的改进算法1.可以将算法改为方案。即文中所有“改进算法”都改为“改进方案”。

2.改进方案主要针对原方案的不足，有几方面改进，如安全性，效率，同态性等。很难用一个名词来完全描述这些内容。所以，用“改进方案”来描述它是一个合适的选择，因此这里可以不做修改。改进方案，分析了算法的安全性，尤其是对抗格基规约攻击的性能。研究了基于改进方案构造同态操作的可行性，并对原方案和到底是改进的“方案”还是“算法”，全文应统一改进方案的主要性能作了对比。最后对同态性构建过程中的经验进行了总结，提出了构建理想（全）同态加密方案的有益思路。

关键词：同态加密；中国剩余定理（CRT）；同态性；格基规约攻击；LLL算法可以将关键词改成LLL算法。这个算法没有中文名称。

中图分类号： TP 309.7 文献标志码：A

英文摘要

Abstract：

The existing （fully） homomorphic encryption schemes fail to meet practical needs for poor efficiency. To explore new resolution for better homomorphic encryption schemes， the possibility to construct homomorphism on a public key encryption scheme in literature based on Chinese Residue Theorem （CRT） was studied. The possibility of the original scheme to construct the addition and multiplication homomorphic operations was investigated. The original scheme was proved to be unsuitable for constructing homomorphic addition and multiplication operations. Several problems concerning security and efficiency existing in the original scheme were analyzed. Then a revised scheme with tougher security under proper configurations was given， as well as its correctness verification. After that， analysis on security and computing complexity of the revised scheme was given， emphasizing on its ability against the lattice reduction attack. Afterwards， the feasibility of building homomorphic operations on the revised scheme was studied and the main performance comparison between the original and the revised schemes was constructed. Finally， experience on building homomorphism was summarized and some advice on constructing an ideal （fully） homomorphic encryption scheme was presented.

英文关键词

Key words：

Homomorphic Encryption （HE）； Chinese Residue Theorem （CRT）； homomorphism；核实是否正确.该关键词正确

2.LLL算法是格理论中的一个著名算法，这个名字是三个人名的第一个字母，但其长度很大，故此处没有写出。又由于其主要作用是格基规约（Lattice Reduction），故将其写成了Lattice Reduction algorithm latticebased reduction attack； LenstraLenstraLovasz （LLL） 缩写与2.3节相应英文不对应，作者核实是否有误？algorithm

0 引言

云计算是未来互联网发展的重要内容之一。在云计算中，为保证安全性，数据必须以密文形式存储并进行处理。所以必须要求经云服务器处理之后的数据能够被解密为对明文作相应处理的结果。全同态加密技术恰好能够满足这种要求。

全同态加密的思想在1978年由Rivest、Adleman和Dertouzos等[1]提出， 其后产生过许多同态加密方案。但这些方案有的只满足加法同态，如各方案，应有文献引用1984年由Goldwasser与Micali提出的中文全称GM （GoldwasserMicali）加密体制[2]；有些只满足乘法同态，如中文全称RSA（Rivest， Shamier， Adleman）方案[3]和El Gamal方案[4]；还有一些能够满足有限次加法与乘法的同态方案，如2005年由BonehGohNissm提出的BGN（Boneh， Goh， Nissm）体制[5]等。这些方案都没有实现真正的全同态，即可以对任意函数作任意次数的计算。

2009年，IBM的研究员Gentry构造出了第一个真正意义上的全同态加密方案――基于理想格的全同态加密方案[6]，但其计算复杂性非常高。随后出现了一些改进方案，如基于整数的同态加密方案[7]，但整体效率仍然很低。

随后产生的第二代同态加密方案[8-12]是基于带错学习问题（Learning With Errors， LWE）问题。2013 年Gentry又提出了一个基于近似特征向量的全同态加密方案[12]，可以看作第三代同态加密方案的代表。但上述方案仅将自举技术作为优化手段，并未实现真正的全同态，只能称为层次型同态方案。目前效率最高的同态加密方案是环LWE上的BGV（Brakerski， Gentry， Vaikuntanathan）中文全称，BGV方案是三个人名的第一个字母组成的。也没有中文名称，通常就称为BGV方案。方案[9，13-14]。

虽然新的方案不断出现，但由于构造（全）同态的方式过于复杂等原因，使得这些方案的效率很难达到实用要求。目前，构造自然方式的、高效率的、安全的是否加括号（全）同态加密方案仍是摆在密码工作者面前的一个重要难题。

解决这个难题的思路主要有两种：一是利用优化技术对已有方案进行改进；二是基于新的公钥加密方案创造新的同态加密方案。由于目前已有的（全）同态加密方案均采用工程方式构造等多种原因，使其效率在理论上很难得到较大提升。因此，考察新的公钥加密方案并研究构造新的（全）同态方案的可能性成为非常有意义的工作。

本文研究了王保仓等[15]提出的基于中国剩余定理（Chinese Residue Theorem，CRT）的快速公钥加密算法，考察了基于原方案构造加法和乘法同态操作的可能性，提出了一个改进方案，分析了改进方案对抗格基规约攻击的性能，考察了基于该算法构建加法和乘法同态操作的可能性。最后对同态性构建过程中的经验进行了总结，提出了构建理想（全）同态加密方案的思路。

1 相关研究

1.1 基于CRT的快速公钥加密方案

文献[15]提出的基于中国剩余定理的快速公钥加密方案的基本算法流程如下。

1.2 题目不恰当两个引理

作为工具，文献[13]给出的吗？两个有用结果分别是指下面的定理1和定理2，不是参考文献里面给出的，而是本文提出并证明的。该节题目可以改为：两个引理。下面的"定理"也可以相应改为"引理"。

本文给出两个引理。

引理1 两个分别为a比特和b比特的二进制数相加，其和最大可能为max{a，b}+1比特。其中a和b为大于0的自然数。

证明 显然，a比特和b比特二进制数能表示的最大值在其所有比特位全取1时取得，故其和最大可能为max{a，b}+1比特。

引理2 两个分别为a比特和b比特的二进制数相乘，其乘积的最大值不会超过（a+b）比特。其中a和b为大于0的自然数。

证明 a比特和b比特的二进制数最大分别为2a-1和2b-1，而对任意大于0的自然数a和b，必有2a+2b≥2。故有2a+2b-1≥1，即-2a-2b+1≤-1。

故有：（2a-1）（2b-1）=2a2b-2a-2b+1≤2a+b-1。而（a+b）bit二进制数能表示的最大值即为2a+b-1。故定理2成立。

2 指文献13中方案吗？文献[15]方案同态性分析

王玉玺等文献[13]之后就是15，缺少对14，文献引用应按顺序[16]给出了该快速公钥加密方案的同态性证明，但其过程和结果存在明显问题。现对该问题给出深入分析。

设明文为m=（m1，m2，…，m5）T和m′=（m′1，m′2，…，m′5）T；加密后的密文分别为：c=是固定的函数还是一般的函数，是否可正？这里应该是固定形式，表示加密操作。应该用正体。文中所有Enc和Dec都应该用正体。Enc（m）和c′=Enc（m′）。

证明 显然，在已知矩阵B（B=A-1）和（s1，s2，…，s6）T的条件下，要恢复出唯一确定的M，相当于求解一个含有6个方程和36个变量的线性方程组并试图得到唯一解。这是不可能成功的，故解密不可能成功。

2.3 不对，前面讲的也是问题文献[15]方案存在的其他问题

除具有难以构造同态加法和乘法操作的缺点之外，文献[15]方案在安全性方面也存在问题。

首先，根据文献[15]方案各变量长度设置，只能保证不等式-pi/2

其次，针对该方案，毕经国等[17]构造了一种规约到中文全称格中近似最短向量问题（Shortest Vector Problem， SVP）的格基规约攻击，构造了一个包含明文和随机数的格向量e，利用Kannan的嵌入技术[18]，把要恢复的明文信息转化为求格L中的最短向量问题。

由于文献[15]方案中明文分段长度（300比特）最多是小于，称不上远小于；这里的300和333都是明文的比特长度。说“远小于”是为了突出强调出现后面结果的原因在于两个比特长度的差距。如果只说小于，可能无法表示出其准确含义。因为如果两个比特长度相差不大，可能不会造成后面的结果。后面向量e的长度远小于随机格L中最短向量的长度是没有问题的。远小于素数pi的长度（333比特），导致向量e的长度远小于随机格L中最短向量的长度。利用这个特点，只要使用中英文与关键词为何不一致，是表示两个含义吗，表示一个含义，关键词已改LLL（LenstraLenstraLovasz， LLL）等算法计算出格L中的近似最短向量，就极有可能找到e，从而恢复出明文。

3 基于CRT的加密方案的改进方案

王玉玺等[16]提出了一个指的是方案[13]吗，如果是，用文献[13]方案表示，“原方案”太没有针对性了文献[15]方案的简化方案，并对其同态性进行了简单分析。但是否应加上根据第2章的分析可知？文献[16]分析过程存在错误，且同态性构建并不完整，存在较多问题。

3.1 改进方案

针对文献[15]方案不足，现提出一个基于CRT的快速公钥加密方案的本文改进的是算法还是方案？改进方案，并对其安全性和同态性进行考察。

文中有一个比较突出的问题，就是关于符号m的写法。在3.1节之前，m表示的是向量，因为这部分在引述文献[13]中的方案。而3.1节之后描述的是本文所提方案，这时候的明文m是一个数，不是向量。所以前面的m应该用黑斜体，而后面应该用普通斜体。

3.3 安全性与效率

攻击者的攻击手段主要有两种，即：从公钥求解出私钥和从密文恢复出明文。对于前者，攻击成功的前提有两个：第一是解决大整数分解难题，只要使n足够大即可有效对抗此类攻击；第二是利用联立丢番图逼近方法求出a2，然后求解私钥。文献[15]已对该方式作了分析，证明了基于该模式的加密方案可以抵抗此类攻击。

下面考察改进方案对抗格基规约攻击的性能。

对于改进方案，构造一个3维格L。它的一组基为：β1=（c0，c，0），β2=（0，n，0），β3=（0，b，1），其中c0为λ比特的整数。已知det（L）=n×c0≈22k+λ。记L中最短向量为v。v2的高斯期望为3/（2是否为常数还是变量，是否为正πe）det（L）1/3≈3/（2πe）・2（2k+λ）/3。记向量e=（c0，r，m），知e∈L且e≤3・2λ。若λ太小，将导致向量e的长度比随机格L中最短向量的长度小很多。在这种情况下，只要通过LLL等算法找到L中的（近似）最短向量，即有很大可能获得e。

由改进方案设置可得k-λ≤5。由此知随机格L中最短向量v的长度与向量e的长度之比大约为：3/（2πe）×2（λ+2k）/3/（3・核实句子是否有误，2λ是在分子上还是分母上，目前式子描述不正确2λ）≈2πe×2（2k-λ）/3≈2（2k-λ）/3+3

只要使k的取值不太大，如约束k≤10，可使得上述向量长度之比小于210，则由上述格基规约攻击得到明文的可能性远小于原方案，从而使改进方案对抗格基规约攻击的能力高于原方案。

改进方案的加密算法使用了一个模乘法和一个模加法，故其计算复杂度约为O（λ2），λ为安全参数。解密算法使用了一个模乘法及一个2阶方阵与向量的乘法，复杂度也是O（λ2）。

3.4 同态性分析

密文加法及乘法定义与针对原方案所作定义一致。

3.4.1 加法同态性

4 结语

本文首先研究了文献核实文献引用标注是否正确[15]提出的基于中国剩余定理（CRT）的快速公钥加密方案的安全性和构建同态操作的可能性，然后针对文献[15]所提方案在安全性、效率及同态性等方面的不足构造了一个改进方案；分析了改进方案的安全性和计算复杂性，阐述了改进方案也不适于构建同态乘法操作的原因；最后给出了构建自然方式的同态加密方案的两个建议。

要构造一个方式自然的（全）同态加密方案，需要找到一个经过严格证明困难性的困难问题，然后逻辑不通，上下文意思不明基于该困难问题，构造一个由明文特定形式映射到方阵形式的单向陷门函数。当然，还需要考虑在这个映射中以合理方式添加随机因素。这应该是构造理想（全）同态加密方案的一个合理思路。

参考文献：

文献已查

[1]RIVEST R L， ADLEMAN L， DERTOUZOS M L. On data banks and privacy homomorphisms [C]// Foundations of Secure Computation. New York： Academic Press， 1978： 169-179.

[2] GOLDWASSER S， MICALI S. Probabilistic encryption [J]. Journal of Computer and System Sciences， 1984， 28（2）： 270-299.

[3] RIVEST R L， SHAMIR A， ADLEMAN L. A method for obtaining digital signatures and publickey cryptosystems [J]. Communications of the ACM， 1978， 21（2）： 120-126.

[4] ElGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms [J]. IEEE Transactions on Information Theory， 1985， 31（4）： 469-472.

[5] BONEH D， GOH EJ， NISSIM K. Evaluating 2DNF formulas on ciphertexts [C]// TCC 2005： Proceedings of the Second Theory of Cryptography Conference on Theory of Cryptography， LNCS 3378. Berlin： Springer， 2005： 325-341.

[6]GENTRY C. Fully homomorphic encryption using ideal lattices [C]// Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York： ACM， 2009： 169-178.

[7]van DIJK M， GENTRY C， HALEVI S， et al. Fully homomorphic encryption over the integers [C]// EUROCRYPT 2010： Proceedings of the 2010 29th Annual International Conference on Advances in Cryptology， LNCS 6110. Berlin：Springer， 2010： 24-43.

[8]BRAKERSKI Z， VAIKUNTANATHAN V. Efficient fully homomorphic encryption from （standard） LWE [C]// Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. Piscataway： IEEE， 2011： 97-106.

[9]BRAKERSKI Z， GENTRY C， VAIKUNTANATHAN V. （Leveled） fully

homomorphic encryption without bootstrapping [J]. ACM Transactions on Computation Theory， 2014， 6（3）： Article 13.

[10]BITRAKERSKI Z. Fully homomorphic encryption without modulus switching from classical GapSVP [C]// CRYPTO 2012： Proceedings of the 32nd Annual Cryptology Conference on Advances in Cryptology， LNCS 7417. Berlin： Springer， 2012： 868-886.

[11]LPEZALT A， TROMER E， VAIKUNTANATHAN V. Onthefly multiparty computation on the cloud via multikey fully homomorphic encryption [C]// STOC12： Proceedings of the 44th Annual ACM Symposium on Theory of Computing. New York： ACM， 2012： 1219-1234.

[12]GENTRY C， SAHAI A， WATERS B. Homomorphic encryption from learning with errors： conceptuallysimpler， asymptoticallyfaster， attributebased [C]// CRYPTO 2013： Proceedings of the 33rd Annual Cryptology Conference on Advances in Cryptology， LNCS 8042. Berlin： Springer， 2013： 75-92.

[13]查不到，作者核实要素是否正确HU Y， CHEN H， LIAN Z. A review of the development and present situation of fully homomorphic encryption [J]. Communications of the CCISA Appendix， 2014， 20（1）： 31-50. （胡予濮，陈虎，连至助.全同态加密发展与现状的综述[J].原文为中文文献还是英文文献，为何刊名用英文资讯安全通讯，2014，20（1）：31-50.）

[14]CHEN Z， WANG J， SONG X. Research of fully homomorphic encryption [J]. Application Research of Computers， 2014， 31（6）： 1624-1631. （陈智罡， 王箭， 宋新霞. 全同态加密研究[J]. 计算机应用研究， 2014，31（6）： 1624-1631.）

[15]WANG B， WEI Y， HU Y. Fast publickey encryption scheme based on the Chinese remainder theorem [J]. Journal of Xian Electronic and Science University， 2008， 35 （3）： 449-454. （王宝仓，韦永壮，胡予濮.基于中国剩余定理的快速公钥加密算法[J]. 西安电子科技大学学报，2008，35（3）： 449-454.）

[16]WANG Y， ZHANG C， ZHANG B. Homomorphic research of fast publickey cryptosystem based on the Chinese remainder theorem [J]. Computer Engineering and Design， 2013， 34 （9）： 3038-3041. （王玉玺，张串绒，张柄虹.基于中国剩余定理的快速公钥算法同态特性研究 [J]. 计算机工程与设计，2013，34（9）： 3038-3041.）

[17]BI J， HAN L， LIU M. Cracking the publickey encryption scheme based on the Chinese remainder theorem [J]， Journal of Beijing University of Technology， 2012， 38 （5）： 768-772. （毕经国，韩立东，刘明洁.基于中国剩余定理的公钥加密算法的破解 [J]，北京工业大学学报，2012，38（5）： 768-772.）

[18]KANNAN R. Minkowskis convex body thermo and integer programming [J]. Mathematics of Operation Research， 1987， 12（3）： 415-440.

[19]SAVAS E， KOC C K. The montgomery modular inverserevisited [J]. IEEE Transactions on Computers， 2000， 49（7）： 763-766.

[20]MICCIANCIO D. A first glimpse of cryptographys Holy Grail [J]. Communications of the ACM， 2010， 53（3）： 96-96.

[21]该条文献网上查不到，作者核实各项要素是否正确LI Z， MA C. Advances in fully homomorphic technologies ― study on application of homomorphic technologies [J]. 核实英文刊名，原文为Chinese password Society Newsletter，是否应为现在的，或Communicaitons of Chinese Association for Crytologic Research， 26是否为卷号？Communicaitons of Chinese Association for Crytologic Research改为Communicaitons of Chinese Association for Crytologic Research 较合适。26是卷号。

Communicaitons of Chinese Association for Crytologic Research， 2013，26（3）： 30-35.