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

针对现有(全)同态加密方案的整体性能不能达到实用要求的问题,为获得新的性能更好的同态加密思路,对基于中国剩余定理(CRT)的快速公钥加密方案的同态性进行了研究。考察了基于原方案构造加法和乘法同态操作的可能性,指出基于原方案不适于构造加法同态操作和乘法同态操作,并分析了原方案在安全性和效率方面存在的几个问题。提出了一个改进方案,分析了算法的安全性,尤其是对抗格基规约攻击的性能。研究了基于改进方案构造同态操作的可行性,并对原方案和改进方案的主要性能作了对比。最后对同态性构建过程中的经验进行了总结,提出了构建理想(全)同态加密方案的思路。

Homomorphism of a public key encryption scheme based on the chinese residue theorem

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.