NTRU格上高效的基于身份的全同态加密体制

doi:10.11959/j.issn.1000-436x.2017008

通信学报 ›› 2017, Vol. 38 ›› Issue (1): 66-75.doi: 10.11959/j.issn.1000-436x.2017008

NTRU格上高效的基于身份的全同态加密体制

段然^1,²,顾纯祥^1,²,祝跃飞¹,郑永辉^1,²,陈莉³

¹ 信息工程大学四院，河南郑州 450002
² 数学工程与先进计算国家重点实验室，江苏无锡 214125
³ 河南财经政法大学网络信息安全研究所，河南郑州 450046

修回日期:2016-12-19 出版日期:2017-01-01 发布日期:2017-01-23
作者简介:段然（1989-），男，山西大同人，信息工程大学博士生，主要研究方向为格密码理论、全同态加密。|顾纯祥（1976-），男，安徽霍山人，信息工程大学教授、硕士生导师，主要研究方向为密码学。|祝跃飞（1962-），男，浙江杭州人，信息工程大学教授、博士生导师，主要研究方向为密码学、网络与信息安全。|郑永辉（1976-），男，江西乐平人，信息工程大学副教授，主要研究方向为密码学。|陈莉（1968-），女，江苏如皋人，河南财经政法大学教授，主要研究方向为信息安全理论与技术。
基金资助:
国家科技支撑计划基金资助项目(2012BAH47B01);国家自然科学基金资助项目(61170234);国家自然科学基金资助项目(61309007);国家自然科学基金资助项目(61502533);河南省科技创新杰出青年基金资助项目(134100510002);河南省基础与前沿技术研究基金资助项目(142300410002);河南省高校科技创新人才支持计划基金资助项目(13HASTIT043)

Efficient identity-based fully homomorphic encryption over NTRU

Ran DUAN^1,²,Chun-xiang GU^1,²,Yue-fei ZHU¹,Yong-hui ZHENG^1,²,Li CHEN³

¹ Fourth Department,PLA Information Engineering University,Zhengzhou 450002,China
² State Key Laboratory of Mathematical Engineering and Advanced Computing,Wuxi 214125,China
³ Institute of Network Information Security,Henan University of Economics and Law,Zhengzhou 450046,China

Revised:2016-12-19 Online:2017-01-01 Published:2017-01-23
Supported by:
The National Science ＆ Technology Pillar Program(2012BAH47B01);The National Natural Science Foun-dation of China(61170234);The National Natural Science Foun-dation of China(61309007);The National Natural Science Foun-dation of China(61502533);Henan Sciences and Technology Innovation Talent Project(134100510002);Henan Foundation and Advanced Technology Research Project(142300410002);Henan University Science and Technology Innovation Talent Support Project(13HASTIT043)

摘要/Abstract

摘要：

全同态加密是目前解决云计算网络数据隐私保护问题的最佳方案，但目前的体制的公钥尺寸普遍较大。首先，通过引入Kullback-Leibler散度的概念，构造一种NTRU格上的基于身份公钥的加密体制，参数分析表明体制具有较小的密钥和密文尺寸，实验数据表明体制具有较高的加解密效率。其次，利用近似特征向量技术，给出一种方法，将基于身份的公钥加密体制转换为基于身份的全同态加密体制，可以进一步减小密文尺寸。和现有体制相比，除了不需要计算密钥，实现真正意义上的基于身份特性以外，还减小了密钥和密文尺寸，提高了计算和传输效率。

关键词: 全同态加密, 基于身份加密, NTRU格, 随机谕示模型, 近似特征向量

Abstract:

Fully homomorphic encryption is the best solution for solving privacy concerns for data over cloud so far,while large public key size is a general shortcoming for existing schemes.First,by introducing the concept of Kullback-Leibler divergence,an identity-based public key scheme over NTRU lattice with modified ciphertext form was proposed.Analysis on parameter setting showed its small key size and ciphertext size,and experiments revealed its high computational efficiency.Second,with the idea of approximate eigenvector,an improved method to convert the scheme into an identity-based fully homomorphic encryption one was put forward to further reduce ciphertext size.Compared with existing schemes,the converted scheme not only abandons evaluation keys to make it fully identity-based,but also has smaller keys and ciphertext,which results in higher computational and transmission efficiency.

Key words: fully homomorphic encryption, identity-based encryption, NTRU lattice, random oracle model, approximate eigenvector

中图分类号:

TP309.7

段然,顾纯祥,祝跃飞,郑永辉,陈莉. NTRU格上高效的基于身份的全同态加密体制[J]. 通信学报, 2017, 38(1): 66-75.

Ran DUAN,Chun-xiang GU,Yue-fei ZHU,Yong-hui ZHENG,Li CHEN. Efficient identity-based fully homomorphic encryption over NTRU[J]. Journal on Communications, 2017, 38(1): 66-75.

图/表 2

参考文献 24

[1]	RIVEST R L , ADLEMAN L , DERTOUZOS M L . On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978,4(11): 169-180.
[2]	GENTRY C , . Fully homomorphic encryption using ideal lattices[C]// 41st Annual ACM Symposium on Theory of Computing (STOC 2009),Bethesda,USA. 2009: 169-178.
[3]	LYUBASHEVSKY V , PEIKERT C , REGEV O . On ideal lattices and learning with errors over rings[J]. Journal of the ACM, 2013,60(6): 43-65.
[4]	BRAKERSKI Z , VAIKUNTANATHAN V . Efficient fully homomorphic encryption from (standard) LWE[J]. SIAM Journal on Computing, 2014,43(2): 831-871.
[5]	TREPACHEVA A , BABENKO L . Known plaintexts attack on polynomial based homomorphic encryption[C]// 7th International Conference on Security of Information and Networks (SIN 2014),Glasgow,UK. 2014.
[6]	YASUDA M , SHIMOYAMA T , KOGURE J ,et al. Secure statistical analysis using RLWE-based homomorphic encryption[C]// 20th Australasian Conference on Information Security and Privacy (ACISP 2015),QUT,Australia. 2015: 471-487.
[7]	汤殿华, 祝世雄, 王林 ,等. 基于 RLWE 的全同态加密方案[J]. 通信学报, 2014,35(1): 173-182.
	TANG D H , ZHU S X , WANG L ,et al. Fully homomorphic encryption scheme from RLWE[J]. Journal on Communications, 2014,35(1): 173-182.
[8]	SHAMIR A , . Identity-based cryptosystems and signature schemes[C]// CRYPTO '84,Santa Barbara,California,USA. 1984: 47-53.
[9]	光焱, 祝跃飞, 费金龙 ,等. 利用容错学习问题构造基于身份的全同态加密体制[J]. 通信学报, 2014,35(2): 111-117.
	GUANG Y , ZHU Y F , FEI J L ,et al. Identity-based fully homomorphic encryption from learning with error problem[J]. Journal on Communications, 2014,35(2): 111-117.
[10]	GENTRY C , SAHAI A , WATERS B . Homomorphic encryption from learning with errors:conceptually-simpler,asymptotically-faster,attribute-based[C]// 33rd Annual International Cryptology Conference (CRYPTO 2013), Santa Barbara,CA,USA, 2013: 75-92.
[11]	HOFFSTEIN J , PIPHER J , SILVERMAN J H . NTRU:a ring-based public key cryptosystem[C]// ANTS III,Portland,Oregon,USA. 1998: 267-288.
[12]	DUCAS L , DURMUS A , LEPOINT T ,et al. Lattice signatures and bimodal Gaussians[C]// 33rd Annual International Cryptology Conference (CRYPTO 2013),Santa Barbara,CA,USA. 2013: 40-56.
[13]	PEIKERT C , . Lattice cryptography for the internet[C]// 6th International Conference on Post-Quantum Cryptography (PQCrypto 2014).Waterloo,ON,Canada. 2014: 197-219.
[14]	LóPEZ-ALT A , TROMER E , VAIKUNTANATHAN V . On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C]// 44th Annual ACM Symposium on Theory of Computing (STOC 2012). Portland,USA, 2012: 1219-1234.
[15]	DUCAS L , LYUBASHEVSKY V , PREST T . Efficient identity-based encryption over NTRU lattices[C]// 20th Annual International Conference on the Theory and Application of Cryptology and Information Security (AsiaCrypt 2014),Kaohsiung,Taiwan (R.O.C.). 2014: 22-41.
[16]	ALBRECHT M R , FAUGERE J C , FITZPATRICK R ,et al. Lazy modulus switching for the BKW algorithm on LWE[C]// 17th IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2014). Buenos Aires,Argentina, 2014: 429-445.
[17]	KIRCHNER P , FOUQUE P A . An improved BKW algorithm for LWE with applications to cryptography and lattices[C]// 35th Annual International Cryptology Conference (CRYPTO 2015). Santa Barbara,CA,USA, 2015: 43-62.
[18]	LYUBASHEVSKY V , PREST T . Quadratic time,linear space algorithms for gram-schmidt orthogonalization and gaussian sampling in structured lattices[C]// 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EuroCrypt 2015). Sofia,Bulgaria, 2015: 789-815.
[19]	LYUBASHEVSKY V , PEIKERT C , REGEV O . A toolkit for ring-LWE cryptography[C]// 32rd Annual International Conference on the Theory and Applications of Cryptographic Techniques (Euro Crypt2013). Athens,Greece, 2013: 35-54.
[20]	REGEV O . On lattices,learning with errors,random linear codes,and cryptography[J]. Journal of the ACM (JACM), 2009,56(6): 34-43.
[21]	MICCIANCIO D , REGEV O . Worst-case to average-case reductions based on gaussian measures[J]. SIAM Journal on Computing, 2007,37(1): 267-302.
[22]	DUCAS L , NGUYEN P Q . Faster Gaussian lattice sampling using lazy floating-point arithmetic[C]// 18th Annual International Conference on the Theory and Application of Cryptology and Information Security (AsiaCrypt 2012). Beijing,China, 2012: 415-432.
[23]	GAMA N , NGUYEN P Q . Predicting lattice reduction[C]// 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EuroCrypt 2008). Istanbul,Turkey, 2008: 31-51.
[24]	MICCIANCIO D . Lattice-based cryptography[M]. US: Encyclopedia of Cryptography and SecurityPress, 2011.

体制	n	lb q	主公钥尺寸/kbit	用户私钥尺寸/kbit	密文尺寸/kbit	加密时间/ms	解密时间/ms
DLP体制	512	23	11.5	11.5	23.5	0.227	0.184
DLP2体制	1 024	32	32	32	64	0.481	0.393
NIBE体制	256	28	7	7	7.03	0.091	0.059

体制	n	lb q	主公钥尺寸	用户私钥尺寸	密文尺寸	运算密钥尺寸	加密时间	解密时间
GZF	927	41	2.69 Gbit	5.94 Mbit	2.97 Mbit	1.22 Tbit	3.12 s	9.01 ms
GZF+任意环	944	42	3.18 Mbit	6.35 Mbit	3.21 Mbit	481.81 Gbit	12.09 ms	8.67 ms
GSW	1 040	47	4.45 Gbit	4.38 Mbit	19.61 Tbit	0	33.24 d	5.18 h
GSW+任意环	1 608	70	329.77 kbit	439.69 kbit	188.79 Gbit	0	13.69 min	2.97 min
GSW+DLP2	2 048	70	140 kbit	280 kbit	76.56 Gbit	0	3.46 min	1.20 min
GSW+NIBE	256	58	14.5 kbit	14.56 kbit	211.90 Mbit	0	1.57 s	0.25 s
NIBFHE	256	61	15.25 kbit	15.31 kbit	121.07 Mbit	0	0.86 s	0.15 s

NTRU格上高效的基于身份的全同态加密体制

Efficient identity-based fully homomorphic encryption over NTRU

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 24

相关文章 14

Metrics

推荐阅读 0

[1]	杨亚涛, 刘德莉, 刘培鹤, 曾萍, 肖嵩. BFV-Blockchainvoting：支持BFV全同态加密的区块链电子投票系统[J]. 通信学报, 2022, 43(9): 100-111.
[2]	田有亮,李秋贤,张铎,王琳杰. 可证明安全的理性委托计算协议[J]. 通信学报, 2019, 40(7): 135-143.
[3]	汤永利,胡明星,刘琨,叶青,闫玺玺. 新的格上基于身份的全同态加密方案[J]. 通信学报, 2017, 38(5): 39-47.
[4]	郑永辉,康元基,顾纯祥,董辉. 环上基于属性的全同态加密体制设计[J]. 通信学报, 2017, 38(4): 55-63.
[5]	孙泽栋,祝跃飞,顾纯祥,郑永辉. 基于RLWE的密钥策略属性加密体制[J]. 通信学报, 2016, 37(Z1): 125-131.
[6]	张怡婷,傅煜川,杨明,罗军舟. 基于PBAC模型和IBE的医疗数据访问控制方案[J]. 通信学报, 2015, 36(12): 200-211.
[7]	任艳丽，蔡建兴，黄春水，谷大武. 基于身份加密中可验证的私钥生成外包算法[J]. 通信学报, 2015, 36(11): 61-66.
[8]	光焱1,2，祝跃飞1，费金龙1,2，顾纯祥1,2，郑永辉1,2. 利用容错学习问题构造基于身份的全同态加密体制[J]. 通信学报, 2014, 35(2): 15-117.
[9]	光焱,祝跃飞,费金龙,顾纯祥,郑永辉. 利用容错学习问题构造基于身份的全同态加密体制[J]. 通信学报, 2014, 35(2): 111-117.
[10]	汤殿华,祝世雄,王林,杨浩淼,范佳. 基于RLWE的全同态加密方案[J]. 通信学报, 2014, 35(1): 173-182.
[11]	李大伟,杨庚,苏弘逸,陈燕俐,杨震. 基于身份的泛在通信隐私保护方案[J]. 通信学报, 2011, 32(9): 44-50.
[12]	付颖芳,张兴,张婷,栾良玉. 无线mesh网络中的虫洞攻击检测研究[J]. 通信学报, 2011, 32(1): 59-65.
[13]	崔永刚,刘玉军. 可公开验证的短密钥公钥加密方案[J]. 通信学报, 2010, 31(3): 45-50.
[14]	邹跃鹏,欧阳丹彤,何丽莉,白洪涛. 基于身份加密的个人安全密钥托管机制[J]. 通信学报, 2009, 30(11A): 75-80.