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

doi:10.11772/j.issn.1001-9081.2015.06.1668

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

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

王会勇^1,2, 孙爽¹, 冯勇³

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 Huiyong^1,2, SUN Shuang¹, FENG Yong³

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

摘要/Abstract

摘要：

针对现有(全)同态加密方案的整体性能不能达到实用要求的问题,为获得新的性能更好的同态加密思路,对基于中国剩余定理(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

中图分类号:

TP309.7

王会勇, 孙爽, 冯勇. 基于中国剩余定理的公钥加密方案同态性[J]. 计算机应用, 2015, 35(6): 1668-1672.

WANG Huiyong, SUN Shuang, FENG Yong. Homomorphism of a public key encryption scheme based on the chinese residue theorem[J]. Journal of Computer Applications, 2015, 35(6): 1668-1672.

参考文献

[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 public-key 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 E-J, NISSIM K. Evaluating 2-DNF 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] LÓPEZ-ALT A, TROMER E, VAIKUNTANATHAN V. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption [C]//STOC'12: 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: conceptually-simpler, asymptotically-faster, attribute-based [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 public-key encryption scheme based on the Chinese remainder theorem [J]. Journal of Xi'an 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 public-key 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 public-key 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. Minkowski's 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 inverse-revisited [J]. IEEE Transactions on Computers, 2000, 49(7): 763-766.
[20] MICCIANCIO D. A first glimpse of cryptography's 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]. Communicaitons of Chinese Association for Crytologic Research, 2013, 26(3): 30-35. (李增鹏, 马春光.全同态加密技术发展——探讨同态加密技术应用于实际 [J].中国密码学会通讯, 2013, 26(3):30-35.)

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	卿欣艺, 陈玉玲, 周正强, 涂园超, 李涛. 基于中国剩余定理的区块链存储扩展模型[J]. 计算机应用, 2021, 41(7): 1977-1982.
[2]	郑尚文, 刘尧, 周潭平, 杨晓元. 优化的基于错误学习问题的CKKS方案[J]. 计算机应用, 2021, 41(6): 1723-1728.
[3]	马敏耀, 刘卓, 徐艺, 吴恋. 隐私保护整数区间位置关系判定问题[J]. 计算机应用, 2020, 40(9): 2657-2664.
[4]	车小亮, 周昊楠, 周潭平, 李宁波, 杨晓元. 基于NTRU的多密钥同态加密方案解密结构[J]. 计算机应用, 2020, 40(7): 1959-1964.
[5]	马敏耀, 吴恋, 刘卓, 徐艺. 隐私保护整数点和区间关系判定问题[J]. 计算机应用, 2020, 40(7): 1983-1988.
[6]	程亚歌, 贾志娟, 胡明生, 公备, 王利朋. 适用于区块链电子投票场景的门限签名方案[J]. 计算机应用, 2019, 39(9): 2629-2635.
[7]	马敏耀, 徐艺, 刘卓. 隐私保护DNA序列汉明距离计算问题[J]. 计算机应用, 2019, 39(9): 2636-2640.
[8]	余卿斐, 涂广升, 李宁波, 周潭平. 多跳多策略属性基全同态加密方案[J]. 计算机应用, 2019, 39(8): 2326-2332.
[9]	涂广升, 杨晓元, 周潭平. 高效的身份基多用户全同态加密方案[J]. 计算机应用, 2019, 39(3): 750-755.
[10]	张恩, 金刚刚. 基于同态加密和Bloom过滤器的云外包多方隐私集合比较协议[J]. 计算机应用, 2018, 38(8): 2256-2260.
[11]	白平, 张薇. 多属性环境下基于容错学习的全同态加密方案[J]. 计算机应用, 2018, 38(5): 1377-1382.
[12]	代小康, 陈长波, 吴文渊. 基于同态门限密码体制的投票协议[J]. 计算机应用, 2018, 38(4): 1036-1040.
[13]	王岩, 侯整风, 章雪琦, 黄梦洁. 基于中国剩余定理的动态门限签名方案[J]. 计算机应用, 2018, 38(4): 1041-1045.
[14]	罗小双, 杨晓元, 李聪, 王绪安. 基于双服务器模型的可公开验证多元多项式外包计算方案[J]. 计算机应用, 2018, 38(2): 321-326.
[15]	李镇林, 张薇, 白平, 王绪安. 基于属性的BGN型密文解密外包方案[J]. 计算机应用, 2017, 37(8): 2287-2291.