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

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

Abstract

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

CLC Number:

TP309.7

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.

Figures/Tables 2

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

体制	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

Efficient identity-based fully homomorphic encryption over NTRU

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 2

References 24

Related Articles 15

Metrics

Recommended 0

[1]	Xiao-wei LI,Deng-qi YANG,Ben-hui CHEN,Yu-qing ZHANG. Two-factor authenticated key agreement protocol based on biometric feature and password [J]. Journal on Communications, 2017, 38(7): 89-95.
[2]	Ruo MO,Jian-feng MA,Xi-meng LIU,Qi LI. Multi-authority ABS supporting dendritic access structure [J]. Journal on Communications, 2017, 38(7): 96-104.
[3]	Cheng SONG,Ming-yue ZHANG,Wei-ping PENG,Zong-pu JIA,Zhi-zhong LIU,Xi-xi YAN. Research on batch anonymous authentication scheme for VANET based on bilinear pairing [J]. Journal on Communications, 2017, 38(6): 49-57.
[4]	Yong-li TANG,Ming-xing HU,Kun LIU,Qing YE,Xi-xi YAN. Novel identity-based fully homomorphic encryption scheme from lattice [J]. Journal on Communications, 2017, 38(5): 39-47.
[5]	Yong-hui ZHENG,Yuan-ji KANG,Chun-xiang GU,Hui DONG. Attribute-based fully homomorphic encryption scheme over rings [J]. Journal on Communications, 2017, 38(4): 55-63.
[6]	Cheng SONG,Ming-yue ZHANG,Wei-ping PENG,Zong-pu JIA,Zhi-zhong LIU,Xi-xi YAN. Research on pairing-free certificateless batch anonymous authentication scheme for VANET [J]. Journal on Communications, 2017, 38(11): 35-43.
[7]	Qing YE,Ming-xing HU,Yong-li TANG,Kun LIU,Xi-xi YAN. Novel hierarchical identity-based encryption scheme from lattice [J]. Journal on Communications, 2017, 38(11): 54-64.
[8]	Ze-dong SUN,Yue-fei ZHU,Chun-xiang GU,Yong-hui1 ZHENG. RLWE-based key-policy ABE scheme [J]. Journal on Communications, 2016, 37(Z1): 125-131.
[9]	Zhen-guo ZHAO. Security analysis and improvement of a certificateless signcryption scheme [J]. Journal on Communications, 2015, 36(3): 75-80.
[10]	. Analysis and improvement of an identity-based signcryption [J]. Journal on Communications, 2015, 36(11): 174-179.
[11]	. Verifiable outsourcing private key generation algorithm in an identity-based encryption scheme [J]. Journal on Communications, 2015, 36(11): 61-66.
[12]	Hong-zhen DU,Qiao-yan WEN. Improved certificateless sequential multi-signature scheme [J]. Journal on Communications, 2015, 36(10): 56-61.
[13]	. Fair multi-party concurrent signature scheme [J]. Journal on Communications, 2014, 35(3): 16-149.
[14]	Qing YE,Yun YANG,Shi-hui ZHENG,Li-wei CHANG,Da XIAO,Yi-xian YANG. Fair multi-party concurrent signature scheme [J]. Journal on Communications, 2014, 35(3): 140-149.
[15]	Yan GUANG,Yue-fei ZHU,Jin-long FEI,Chun-xiang GU,Yong-hui ZHENG. Identity-based fully homomorphic encryption from learning with error problem [J]. Journal on Communications, 2014, 35(2): 111-117.