计算机应用 ›› 2015, Vol. 35 ›› Issue (6): 1668-1672.DOI: 10.11772/j.issn.1001-9081.2015.06.1668

• 信息安全 • 上一篇    下一篇

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

王会勇1,2, 孙爽1, 冯勇3   

  1. 1. 中国科学院 成都计算机应用研究所, 成都 610041;
    2. 桂林电子科技大学 数学与计算科学学院, 广西 桂林 541004;
    3. 中国科学院 重庆绿色智能技术研究院, 重庆 400714
  • 收稿日期:2014-12-31 修回日期:2015-04-15 发布日期:2015-06-12
  • 通讯作者: 王会勇(1977-),男,山东诸城人,讲师,博士,主要研究方向:公钥密码学、网络信息安全;why608@163.com
  • 作者简介:孙爽(1988-),女,山东淄博人,硕士,主要研究方向:公钥密码学、同态加密、信息安全;冯勇(1965-),男,四川成都人,研究员,博士生导师,主要研究方向:符号数值计算、格约化算法、信息安全。
  • 基金资助:

    国家973计划项目(2011CB302402,2011CB302400);国家自然科学基金资助项目(61363069);广西壮族自治区自然科学基金资助项目(61462017,2014GXNSFAA118364)。

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

WANG Huiyong1,2, SUN Shuang1, FENG Yong3   

  1. 1. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu Sichuan 610041, China;
    2. School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin Guangxi 541004, China;
    3. Chongqing Institute of Green Intelligent Technology, Chinese Academy of Sciences, Chongqing 400714, China
  • Received:2014-12-31 Revised:2015-04-15 Published:2015-06-12

摘要:

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

关键词: 同态加密, 中国剩余定理, 同态性, 格基规约攻击, LLL算法

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, lattice-based reduction attack, Lenstra-Lenstra-Lovasz (LLL) algorithm

中图分类号: