新的格上基于身份的全同态加密方案

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

Abstract

Abstract:

The previous identity-based homomorphic encryption schemes from lattice was analyzed.That the high complexity in previous schemes was mainly caused by trapdoor generation and preimage sampling was pointed out.A new solution was proposed.A novel identity-based encryption scheme from lattice by combining new trapdoor function and dual-LWE algorithm organically was constructed,and it was transformed to an identity-based fully homomorphic encryption scheme from lattice by employing the idea of eigenvector.Comparative analysis shows that the scheme’s complexity of trapdoor generation has a significant reduction,the complexity of preimage sampling has a nearly three-fold reduction,and the SIVP approximation factor has a $\sqrt{m}$ times reduction.The security of the proposed scheme strictly reduces to the hardness of decisional learning with errors problem in the standard model.

Key words: lattice, fully homomorphic encryption, identity-based encryption, standard model, cryptography

CLC Number:

TP309

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.

Figures/Tables 3

符号	意义
A^m×n	m行n列矩阵
A _i	矩阵A的第i行
u	向量，默认为列向量形式
u[i]	向量u的第i个分量
u^T	向量u的转置
$‖ S ‖$	向量集合S 的长度，等于其中所有向量欧几里得范数的最大值
$‖ \tilde{S} ‖$	向量集合S 的Gram-Schmidt范数的最大值
s ₁ (R)	矩阵R的最大奇异值
negl(n)	n的可忽略函数：f(n)＜(n^?c)，c 为常数
poly (n)	n的多项式函数：f(n)=O(n^c)，c 为常数

比较参数	Agrawal 2010方案	Agrawal 2012方案	Wang方案	本文方案
m	6nlbq	5nlbq	6nlbq	2nlbq
σ	$m ω (\sqrt{lb n})$	mlbmω (lbn )	(m+6)ω (lbn )	$\sqrt{m} ω (\sqrt{lb n})$
q	$\sqrt{n m^{3}} ω (lb n)$	$\sqrt{n m^{3}} lb m ω {(lb n)}^{\frac{3}{2}}$	$(\sqrt{n m^{3}} + 6 \sqrt{n m}) ω {(lb n)}^{\frac{3}{2}}$	$m \sqrt{n} ω (lb n)$
β	$\sqrt{m^{3}} ω (\sqrt{lb n})$	$\sqrt{m^{3}} lb m ω (lb n)$	$(\sqrt{n m^{3}} + 6 \sqrt{n m}) ω (lb n)$	$m ω (\sqrt{lb n})$
α	${(\sqrt{m^{3}} ω (lb n))}^{- 1}$	${(\sqrt{m^{3}} lb m ω {(lb n)}^{\frac{3}{2}})}^{- 1}$	${((\sqrt{m^{3}} + 6 \sqrt{n m}) ω {(lb n)}^{\frac{3}{2}})}^{- 1}$	${(m ω (lb n))}^{- 1}$

References 21

[1]	RIVEST R , ADLEMAN L , DERTOUZOS M . On data banks and privacy homomorphisms[C]// IEEE 17nd Annual Symposium on Foundations of Computer Science (FOCS1978). 1978: 169-177.
[2]	GENTRY C , . Fully homomorphic encryption using ideal lattices[C]// The 41rd ACM Symposium on Theory of Computing (STOC2009). 2009: 169-178.
[3]	DUCAS L , MICCIANCIO D.FHEW . Bootstrapping homomorphic encryption in less than a second[C]// Advances in Cryptology EUROCRYPT 2016. 2015: 617-640.
[4]	BRAKERSKI Z , PERLMAN R . Lattice-based fully dynamic multi-key FHE with short ciphertexts[C]// Advances in Cryptology CRYPTO 2016. 2016: 190-213.
[5]	NUIDA K , KUROSAWA K . (Batch) Fully homomorphic encryption over integers for non-binary message spaces[C]// Advances in Cryptology EUROCRYPT 2015. 2015: 537-555.
[6]	光焱, 祝跃飞, 费金龙 ,等. 利用容错学习问题构造基于身份的全同态加密体制[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.
[7]	康元基, 顾纯祥, 郑永辉 ,等. 利用特征向量构造基于身份的全同态加密体制[J]. 软件学报, 2016,27(6): 1487-1497.
	KANG Y J , GU C X , ZHENG Y H ,et al. Identity-based fully homomorphic encryption from eigenvector[J]. Journal of Software, 2016,27(6): 1487-1497.
[8]	GENTRY C , SAHAI A , WATERS B.Homomorphic encryption from learning with errors . Conceptually-simpler,asymptotically-faster,attribute-based[C]// Advances in Cryptology CRYPTO 2013. 2013: 75-92.
[9]	CLEAR M , MCGOLDRICK C . Multi-identity and multi-key leveled FHE from learning with errors[C]// Advances in Cryptology CRYPTO 2015. 2015: 630-656.
[10]	GENTRY C , PEIKERT C , VAIKUNTANATHAN V . Trapdoors for hard lattices and new cryptographic constructions[C]// The 40th ACM Symposium on Theory of Computing(STOC2008). 2008: 197-206.
[11]	AJTAIM . Generating hard instances of the short basis problem[C]// Automata,Languages and Programming(ICALP1999). 1999: 1-9.
[12]	AGRAWAL S , BONEHD , BOYEN X . Efficient lattice (H)IBE in the standard model[C]// Advances in Cryptology EUROCRYPT2010. 2010: 553-572.
[13]	APON D , FAN X , LIU F H . Fully-secure lattice-based IBE as compact as PKE[R]. IACRePrint Cryptography Archive, 2016.
[14]	YAMADA S , . Adaptively secure identity-based encryption from lattices with asymptotically shorter public parameters[C]// Advances in Cryptology EUROCRYPT 2016. 2016: 32-62.
[15]	ALWEN J , PEIKERT C . Generating shorter bases for hard random lattices[C]// The 26th International Symposium on Theoretical Aspects of Computer Science. 2009: 535-553.
[16]	MICCIANCIO D , PEIKERT C . Trapdoors for lattices,simpler,tighter,faster,smaller[C]// Advances in Cryptology EUROCRYPT 2012. 2012: 700-718.
[17]	REGEV O . On lattices,learning with errors,random linear codes,and cryptography[J]. The Annual ACM Symposium on Theory of Computing, 2009,56(6): 84-93.
[18]	AGRAWAL S , BOYEN X , VAIKUNTANATHAN V ,et al. Functional encryption for threshold functions(or fuzzy IBE) from lattices[C]// The 15th International Conference on Practice and Theory in Public Key Cryptography. 2012: 280-297.
[19]	WANG F H , LIU Z H , WANG C X . Full secure identity-based encryption scheme with short public key size over lattices in the standard model[J]. The International Journal of Computer Mathematics, 2016,93(6): 854-863.
[20]	DODIS Y , OSTROVSKY R , REYZIN L . Fuzzy extractors.How to generate strong keys from biometrics and other noisy data[J]. The Society for Industrial and Applied Mathematics (SIAM), 2008,38(1): 97-139.
[21]	PEIKERT C , . An efficient and parallel gaussian sampler for lattices[C]// Advances in Cryptology CRYPTO 2010. 2010: 80-97.

Metrics

Recommended 0

No Suggested Reading articles found!

IBFHE方案	标准模型	运算密钥	陷门生成复杂度(×10¹⁰)	原像采样复杂度(×10¹⁰)	公钥尺寸/MB	私钥尺寸/KB
GY方案	否	有	乘次数64.65加次数64.65	乘次数69.04加次数68.80	50.4	76.2
Clear方案	否	无	乘次数64.65加次数64.65	乘次数69.04加次数68.80	472.6	1.66
本文方案	是	无	乘次数1.374加次数1.374	乘次数23.15加次数23.15	472.5	1.66

Novel identity-based fully homomorphic encryption scheme from lattice

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 21

Related Articles 15

Metrics

Recommended 0

[1]	Huawei HUANG. Security analysis of public-key cryptosystems based on matrix action problem against quantum attack [J]. Journal on Communications, 2023, 44(3): 220-226.
[2]	Ziyuan WANG, Ruizhong DU. Certificateless public key cryptography based provable data possession scheme in edge environment [J]. Journal on Communications, 2022, 43(7): 62-72.
[3]	Zhu WANG, Siqi YANG, Fenghua LI, Kui GENG, Tingting PENG, Mengyao SHI. Efficient and provably-secure certificateless sequential aggregate signature scheme [J]. Journal on Communications, 2022, 43(5): 58-67.
[4]	Huanhuan LIAN, Huiying HOU, Yunlei ZHAO. Post-quantum verifier-based three-party password authenticated key exchange protocol [J]. Journal on Communications, 2022, 43(4): 95-106.
[5]	Bin LI, Xiaojie CHEN, Feng FENG, Qinglei ZHOU. FPGA multi-unit parallel optimization and implementation of post-quantum cryptography CRYSTALS-Kyber [J]. Journal on Communications, 2022, 43(2): 196-207.
[6]	Yuanbo GUO, Anqi YIN. Research on password-authenticated key exchange protocol over lattices [J]. Journal on Communications, 2022, 43(12): 172-187.
[7]	Youheng DONG, Geng ZHAO, Yingjie MA. Two-dimensional pseudo-random coupled map lattices system based on partitioned elementary cellular automata and its dynamic properties [J]. Journal on Communications, 2022, 43(1): 71-82.
[8]	Youliang TIAN, Xiaoxia JIANG. Fair and rational delegation of computation in the universally composable framework [J]. Journal on Communications, 2021, 42(9): 106-119.
[9]	Hongxia HOU, Mingrui ZHANG, Yanqi ZHAO, Xiaoli DONG. ID-based ring signature on prime order group from asymmetric pairing [J]. Journal on Communications, 2021, 42(9): 155-164.
[10]	Hui LIU, Xinyan LIU, Yan XU, Hong ZHONG, Meng WANG. Privacy protection of warning message publishing protocol in VANET [J]. Journal on Communications, 2021, 42(8): 120-129.
[11]	Jiangtao DONG, Peiwen YAN, Ruizhong DU. Verifiable access control scheme based on unpaired CP-ABE in fog computing [J]. Journal on Communications, 2021, 42(8): 139-150.
[12]	Huaqun WANG, Zhe LIU, Debiao HE, Jiguo LI. Identity-based provable data possession scheme for multi-source IoT terminal data in public cloud [J]. Journal on Communications, 2021, 42(7): 52-60.
[13]	Wenbo ZHANG, Wenhua HUANG, Jingyu FENG. Secure communication mechanism for VSN based on certificateless signcryption [J]. Journal on Communications, 2021, 42(7): 128-136.
[14]	Fei TANG, Jiali BAO, Yonghong HUANG, Dong HUANG, Huili WANG. Multi-authority attribute-based identification scheme [J]. Journal on Communications, 2021, 42(3): 220-228.
[15]	Bin WANG, Si CHEN, Jiadong CHEN, Xing WANG. DWB-AES: an implementation of dynamic white-box based on AES [J]. Journal on Communications, 2021, 42(2): 177-186.