基于NTRU的全同态加密方案

doi:10.3969/j.issn.0372-2112.2018.04.023

电子学报 ›› 2018, Vol. 46 ›› Issue (4): 938-944.DOI: 10.3969/j.issn.0372-2112.2018.04.023

基于NTRU的全同态加密方案

李子臣¹, 张卷美², 杨亚涛^2,3, 张峰娟^2,3

1. 北京印刷学院, 北京 102600;
2. 北京电子科技学院, 北京 100070;
3. 西安电子科技大学通信工程学院, 陕西西安 710071

收稿日期:2016-12-11 修回日期:2017-07-28 出版日期:2018-04-25
- 通讯作者:
- 张卷美, 杨亚涛
- 作者简介:
- 李子臣 男,1965年9月出生,河南焦作人.现为北京印刷学院教授.研究领域为公钥密码学、同态加密.E-mail:lizichen@bigc.edu.cn;张峰娟 女,1992年1月出生,河南濮阳人.2017年毕业于西安电子科技大学,获得硕士学位.研究方向为密码学、信息安全、同态密码.E-mail:1185238590@qq.com
- 基金资助:
- 国家自然科学基金 (No.61370188）; "十三五"国家密码发展基金 (No.MMJJ20170110）

A Fully Homomorphic Encryption Scheme Based on NTRU

LI Zi-chen¹, ZHANG Juan-mei², YANG Ya-tao^2,3, ZHANG Feng-juan^2,3

1. Beijing Institute of Graphic Communication, Beijing 102600, China;
2. Beijing Electronic Science & Technology Institute, Beijing 100070, China;
3. School of Telecommunications Engineering, Xidian University, Xi'an, Shaanxi 710071, China

Received:2016-12-11 Revised:2017-07-28 Online:2018-04-25 Published:2018-04-25
- Corresponding author:
- ZHANG Juan-mei, YANG Ya-tao

摘要/Abstract

摘要： 本文提出一种基于公钥密码体制（Number Theory Research Unit，NTRU）选择明文攻击（Chosen Plaintext Attack，CPA）可证明安全的全同态加密方案.首先，对NTRU的密钥生成算法进行改进，通过格上的高斯抽象算法生成密钥对，避免了有效的格攻击，同时，没有改变密钥的分布.然后，基于改进的NTRU加密算法，利用Flattening技术，构造了一个全同态加密体制，并在标准模型下证明方案是选择明文攻击不可区分性IND-CPA安全的.

关键词: 全同态加密, 公钥密码体制NTRU, 高斯抽样算法, 可证明安全

Abstract:

A fully homomorphic encrgption scheme was presented based on number theory research unit (NTRU), which is provable security about indistinguishable chosen plaintext attack (IND-CPA). Firstly, to avoid the effective lattice attacks, we modified the key generation algorithm of NTRU by Gaussian abstraction algorithm of lattices, and the distribution of the key is not changed. Then, we proposed a new homomorphic encryption scheme based on the improved NTRU encryption algorithm by using the Flattening technique. Its IND-CPA security was proved strictly under the standard model.

Key words: fully homomorphic encryption, number theory research unit, Gaussian abstraction algorithm, provable security

中图分类号:

TP309.7

李子臣, 张卷美, 杨亚涛, 张峰娟. 基于NTRU的全同态加密方案[J]. 电子学报, 2018, 46(4): 938-944.

LI Zi-chen, ZHANG Juan-mei, YANG Ya-tao, ZHANG Feng-juan. A Fully Homomorphic Encryption Scheme Based on NTRU[J]. Acta Electronica Sinica, 2018, 46(4): 938-944.

参考文献

[1] RIVEST R L,ADLEMAN L,DERTOUZOS M L.On data banks and privacy homomorphisms[A].Foundations of Secure Computation[C].USA:Academia Press,1978.169-179.
[2] GAMAL T E.A public key cryptosystem and a signature scheme based on discrete logarithms[A].Proceedings of CRYPTO 84 on Advances in Cryptology[C].New York:Springer-Verlag,1985.10-18.
[3] GOLDWASSER S,MICALI S.Probabilistic encryption & how to play mental poker keeping secret all partial information[A].Proceedings of Fourteenth ACM Symposium on Theory of Computing[C].New York:ACM,1982.365-377.
[4] PAILLIER P.Public-key cryptosystems based on composite degree residuosity classes[J].Lecture Notes in Computer Science,1999,547(1):223-238.
[5] RIVEST R,SHAMIR A,ADLEMAN L M.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the ACM,1978,26(2):96-99.
[6] GENTRY C.A Fully Homomorphic Encryption Scheme[D].USA:Stanford University,2009.
[7] DIJK M V,GENTRY C,HALEVI S,et al.Fully homomorphic encryption over the integers[J].Lecture Notes in Computer Science,2009,(4):24-43.
[8] BRAKERSKI Z,VAIKUNTANATHAN V.Efficient fully homomorphic encryption from (standard) LWE[A].Proceedings of Foundations of Computer Science[C].USA:IEEE,2010.97-106.
[9] MANDAL A,TIBOUCHI M.Fully homomorphic encryption over the integers with shorter public keys[A].Proceedings of Conference on Advances in Cryptology[C].New York:Springer-Verlag,2011.487-504.
[10] CORON J,NACCACHE D,TIBOUCHI M.Public key compression and modulus switching for fully homomorphic encryption over the integers[A].Proceedings of International Conference on Theory and Applications of Cryptographic Techniques[C].New York:Springer-Verlag,2012.446-464.
[11] YAGISAWA M.Fully homomorphic encryption without bootstrapping[J].ACM Transactions on Computation Theory,2015,6(3):1-36.
[12] HALEVI S,SHOUP V.HElib,Homomorphic Encryption Library[OL].http://shaih.github.io/HElib/,2012.
[13] 李顺东,王道顺.基于同态加密的高效多方保密计算[J].电子学报,2013,41(4):798-803. LI Shun-dong,WANG Dao-shun.Efficient secure multiparty computation based on homomorphic encryption[J].Acta Electronica Sinica,2013,41(4):798-803.(in Chinese)
[14] 辛丹,顾纯祥,郑永辉,光焱,康元基.利用RLWE构造基于身份的全同态加密体制[J].电子学报,2016,44(12):442887-2893. XIN Dan,GU Chun-xiang,ZHENG Yong-hui,GUANG Yan,KANG Yuan-ji.Identity-based fully homomorphic encryption from ring learning with errors problem[J].Acta Electronica Sinica,2016,44(12):2887-2893.(in Chinese)
[15] CHEN H,YUPU H,LIAN Z.Double batch for RLWE-based leveled fully homomorphic encryption[J].Chinese Journal of Electronics,2015,24(3):661-666.
[16] HOFFSTEIN J,PIPHER J,SILVERMAN J H.NTRU:a ring-based public key cryptosystem[A].Proceedings of the 3rd International Symposium on Algorithmic Number Theory[C].Berlin:Springer,1998.267-288.
[17] 杨铭,曹云飞.NTRU的应用前景分析及展望[J].信息安全与通信保密,2007,(8):36-38. YANG Ming,CAO Yun-fei.Application prospect and analysis of NTRU[J].Information Security and Communications Privacy,2007,(8):36-38.(in Chinese)
[18] TROMER E,VAIKUNTANATHAN V.On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[A].Proceedings of Forty-Fourth ACM Symposium on Theory of Computing[C].New York,ACM,2012.1219-1234.
[19] GENTRY C,SAHAI A,WATERS B.Homomorphic Encryption from Learning with Errors:Conceptually-Simpler,Asymptotically-Faster,Attribute-Based[M].Berlin:Springer,2013.75-92.
[20] GENTRY C,PEIKERT C,VAIKUNTANATHAN V.Trapdoors for hard lattices and new cryptographic constructions[A].Proceedings of DBLP[C].Germany:DBLP,2008.197-206.
[21] LYUBASHEVSHY V,PEIKERT C,REGEV O.On ideal lattice and learning with errors over rings[A].Proceedings of Eurocrypt 2010[C].New York:Springer-Verlag,2010.1-23.
[22] 张建航,贺健,胡予濮.基于R-LWE问题的新型NTRU加密方案[J].电子科技,2012,25(5):76-78. ZHANG Jian-hang,HE Jian,HU Yu-pu.A novel NTRU encryption scheme based on R-LWE problem[J].Electronic Science and Technology,2012,25(5):76-78.(in Chinese)
[23] STEINFELD R.Making NTRU as secure as worst-case problems over ideal lattices[A].Proceedings of International Conference on Theory and Applications of Cryptographic Techniques:Advances in Cryptology[C].New York:Springer-Verlag,2011.27-47.

基于NTRU的全同态加密方案

A Fully Homomorphic Encryption Scheme Based on NTRU

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	尹安琪, 曲彤洲, 郭渊博, 汪定, 陈琳, 李勇飞. 格上基于密文标准语言的可证明安全两轮口令认证密钥交换协议[J]. 电子学报, 2022, 50(5): 1140-1149.
[2]	侯红霞, 杨波, 张丽娜, 张明瑞. 安全的两方协作SM2签名算法[J]. 电子学报, 2020, 48(1): 1-8.
[3]	李秋贤, 田有亮, 王缵. 基于全同态加密的理性委托计算协议[J]. 电子学报, 2019, 47(2): 470-474.
[4]	段然, 顾纯祥, 祝跃飞, 郑永辉, 陈莉. 一种NTRU格上基于身份全同态加密体制设计[J]. 电子学报, 2018, 46(10): 2410-2417.
[5]	辛丹, 顾纯祥, 郑永辉, 光焱, 康元基. 利用RLWE构造基于身份的全同态加密体制[J]. 电子学报, 2016, 44(12): 2887-2893.
[6]	张俊伟, 陈治平, 马建峰, 杨力. 可证明安全的基于位置的Prover-to-Prover密钥交换协议[J]. 电子学报, 2016, 44(1): 14-20.
[7]	袁科, 刘哲理, 贾春福, 杨骏, 吕述望. 一对多场景下的公钥时控性可搜索加密[J]. 电子学报, 2015, 43(4): 760-768.
[8]	张宇, 陈晶, 杜瑞颖, 周庆, 郑明辉. 适于车载网安全通信的高效签密方案[J]. 电子学报, 2015, 43(3): 512-517.
[9]	郭奕旻, 李顺东, 陈振华, 刘新. 一种轻量级隐私保护的RFID群组证明协议[J]. 电子学报, 2015, 43(2): 289-292.
[10]	马骏, 郭渊博, 马建峰, 刘西蒙, 李琦. 物联网感知层基于资源分层的多用户访问控制方案[J]. 电子学报, 2014, 42(1): 28-35.
[11]	裴士辉;赵永哲;赵宏伟. 基于遍历矩阵的公钥加密方案[J]. 电子学报, 2010, 38(8): 1908-1913.
[12]	徐津;温巧燕;王大印. 一种新的一阶段加密认证模式[J]. 电子学报, 2009, 37(10): 2187-2192.
[13]	粟栗, 崔国华, 李俊, 郑明辉. 签密的仲裁安全与仲裁安全的签密方案[J]. 电子学报, 2007, 35(11): 2117-2122.
[14]	李进;张方国;王燕鸣. 两个高效的基于分级身份的签名方案[J]. 电子学报, 2007, 35(1): 150-152.
[15]	王念平, 金晨辉, 余昭平. 非平衡Feistel网络的线性可证明安全性的进一步分析[J]. 电子学报, 2006, 34(10): 1799-1802.