摘要：针对现有（全）同态加密方案的整体性能不能达到实用要求的问题，为获得新的性能更好的同态加密思路，对基于中国剩余定理（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 引言
云计算是未来互联网发展的重要内容之一。在云计算中，为保证安全性，数据必须以密文形式存储并进行处理。所以必须要求经云服务器处理之后的数据能够被解密为对明文作相应处理的结果。全同态加密技术恰好能够满足这种要求。
虽然新的方案不断出现，但由于构造（全）同态的方式过于复杂等原因，使得这些方案的效率很难达到实用要求。目前，构造自然方式的、高效率的、安全的是否加括号（全）同态加密方案仍是摆在密码工作者面前的一个重要难题。
解决这个难题的思路主要有两种：一是利用优化技术对已有方案进行改进；二是基于新的公钥加密方案创造新的同态加密方案。由于目前已有的（全）同态加密方案均采用工程方式构造等多种原因，使其效率在理论上很难得到较大提升。因此，考察新的公钥加密方案并研究构造新的（全）同态方案的可能性成为非常有意义的工作。
本文研究了王保仓等[15]提出的基于中国剩余定理（Chinese Residue Theorem，CRT）的快速公钥加密算法，考察了基于原方案构造加法和乘法同态操作的可能性，提出了一个改进方案，分析了改进方案对抗格基规约攻击的性能，考察了基于该算法构建加法和乘法同态操作的可能性。最后对同态性构建过程中的经验进行了总结，提出了构建理想（全）同态加密方案的思路。
1 相关研究
1.1 基于CRT的快速公钥加密方案
文献[15]提出的基于中国剩余定理的快速公钥加密方案的基本算法流程如下。
本文给出两个引理。
引理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的自然数。
2 指文献13中方案吗？文献[15]方案同态性分析
王玉玺等文献[13]之后就是15，缺少对14，文献引用应按顺序[16]给出了该快速公钥加密方案的同态性证明，但其过程和结果存在明显问题。现对该问题给出深入分析。
2.3 不对，前面讲的也是问题文献[15]方案存在的其他问题
除具有难以构造同态加法和乘法操作的缺点之外，文献[15]方案在安全性方面也存在问题。
由于文献[15]方案中明文分段长度（300比特）最多是小于，称不上远小于；这里的300和333都是明文的比特长度。说“远小于”是为了突出强调出现后面结果的原因在于两个比特长度的差距。如果只说小于，可能无法表示出其准确含义。因为如果两个比特长度相差不大，可能不会造成后面的结果。后面向量e的长度远小于随机格L中最短向量的长度是没有问题的。远小于素数pi的长度（333比特），导致向量e的长度远小于随机格L中最短向量的长度。利用这个特点，只要使用中英文与关键词为何不一致，是表示两个含义吗，表示一个含义，关键词已改LLL（LenstraLenstraLovasz， LLL）等算法计算出格L中的近似最短向量，就极有可能找到e，从而恢复出明文。 3 基于CRT的加密方案的改进方案
3.1 改进方案
针对文献[15]方案不足，现提出一个基于CRT的快速公钥加密方案的本文改进的是算法还是方案？改进方案，并对其安全性和同态性进行考察。
文中有一个比较突出的问题，就是关于符号m的写法。在3.1节之前，m表示的是向量，因为这部分在引述文献[13]中的方案。而3.1节之后描述的是本文所提方案，这时候的明文m是一个数，不是向量。所以前面的m应该用黑斜体，而后面应该用普通斜体。
3.3 安全性与效率
攻击者的攻击手段主要有两种，即：从公钥求解出私钥和从密文恢复出明文。对于前者，攻击成功的前提有两个：第一是解决大整数分解难题，只要使n足够大即可有效对抗此类攻击；第二是利用联立丢番图逼近方法求出a2，然后求解私钥。文献[15]已对该方式作了分析，证明了基于该模式的加密方案可以抵抗此类攻击。
下面考察改进方案对抗格基规约攻击的性能。
改进方案的加密算法使用了一个模乘法和一个模加法，故其计算复杂度约为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.
[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.
[9]BRAKERSKI Z， GENTRY C， VAIKUNTANATHAN V. （Leveled） fully
homomorphic encryption without bootstrapping [J]. ACM Transactions on Computation Theory， 2014， 6（3）： Article 13.
[20]MICCIANCIO D. A first glimpse of cryptographys Holy Grail [J]. Communications of the ACM， 2010， 53（3）： 96-96.