对一个格基身份签名方案的分析和改进

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

通信学报 ›› 2015, Vol. 36 ›› Issue (5): 104-111.doi: 10.11959/j.issn.1000-436x.2015136

对一个格基身份签名方案的分析和改进

杨春丽^1,²,闫建华^1,^2,³,郑世慧^1,²,王励成^1,²,杨榆^1,²

¹ 北京邮电大学信息安全中心，北京 100876
² 北京邮电大学灾备技术国家工程实验室，北京 100876
³ 鲁东大学信息与电气工程学院，山东烟台 264025

出版日期:2015-05-20 发布日期:2015-07-17
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金中日韩A3前瞻计划基金资助项目;中央高校基本科研业务费专项基金资助项目;中央高校基本科研业务费专项基金资助项目;中央高校基本科研业务费专项基金资助项目

Analysis and improvement of an identity-based signature scheme from lattices

ANGChun-li Y^1,²,ANJian-hua Y^1,^2,³,HENGShi-hui Z^1,²,ANGLi-cheng W^1,²,ANGYu Y^1,²

¹ Information Security Research Center,Beijing University of Posts and Telecommunications,Beijing 100876,China
² National Engineering Laboratory for Disaster Backup and Recovery,Beijing University of Posts and Telecommunications,Beijing 100876,China
³ School of Information and Electric Engineering,Ludong University,Yantai 264025,China

Online:2015-05-20 Published:2015-07-17
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The NSFC A3 Foresight Program;The Fundamental Research Funds for the Central Universities;The Fundamental Research Funds for the Central Universities;The Fundamental Research Funds for the Central Universities

摘要/Abstract

摘要：

首先分析了Liu等人2013年给出的一个格基身份签名（IBS）方案在安全性证明中存在的问题，进而说明方案的证明达不到作者所宣称的选择身份和自适应选择消息攻击下的强不可伪造性。其次，使用Boyen10签名技术（PKC 2010）对此方案中签名算法进行改进，并在标准模型下证明了改进方案在选择身份和自适应选择消息攻击下具有强不可伪造性的安全性质。另外，对比分析了改进的方案和其他IBS方案的效率和安全性。

关键词: 基于身份的签名, 强不可伪造, 标准模型, 格

Abstract:

Liu et al proposed an identity-based signature from lattices in 2013,and proved that it can achieve strong un-forgeability in the standard model.Through analysis,the security proof of this scheme has some defect,and then show that the scheme cannot prove the strong unforgeability under selective identity and adaptive chosen-message attacks.Then,using Boyen signing technique (PKC 2010) inpoves the signing algorithm,and proves the strong unforgeability under selective identity and adaptive chosen-message attacks (SU-sID-CMA) in the standard model.In addition,it com-pares the efficiency and security of the scheme and the other identity-based signatures from lattices.

Key words: identity-based signature, strong unforgeability, standard model, lattices

杨春丽,闫建华,郑世慧,王励成,杨榆. 对一个格基身份签名方案的分析和改进[J]. 通信学报, 2015, 36(5): 104-111.

ANGChun-li Y,ANJian-hua Y,HENGShi-hui Z,ANGLi-cheng W,ANGYu Y. Analysis and improvement of an identity-based signature scheme from lattices[J]. Journal on Communications, 2015, 36(5): 104-111.

图/表 1

参考文献 25

[1]	SHAMIR A . Identity-based cryptosystems and signature schemes[A]. Advances in Cryptology[C]. Springer Berlin Heidelberg, 1985. 47-53.
[2]	BONEH D , FRANKLIN M . Identity-based cryptosystems and signature schemes[A]. Advances in Cryptology CRYPTO 2001[C]. Springer Berlin Heidelberg, 2001. 213-229.
[3]	WATERS B . Efficient identity-based encryption without random oracles[A]. Advances in Cryptology–EUROCRYPT 2005[C]. Springer Berlin Heidelberg, 2005. 114-127.
[4]	PATERSON K G , SCHULDT J C N . Efficient identity-based signatures secure in the standard model[A]. Information Security and Privacy[C]. Springer Berlin Heidelberg, 2006. 207-222.
[5]	SHOR P W . Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997,26(5): 1484-1509.
[6]	AJTAI M . Generating hard instances of lattice problems[A]. Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing[C]. ACM, 1996. 99-108.
[7]	REGEV O . On lattices,learning with errors,random linear codes,and cryptography[J]. Journal of the ACM (JACM), 2009,56(6): 34-.
[8]	MICCIANCIO D , PEIKERT C . Trapdoors for lattices:simpler,tighter,faster,smaller[A]. Advances in Cryptology–EUROCRYPT 2012[C]. Springer Berlin Heidelberg, 2012. 700-718.
[9]	GENTRY C , PEIKERT C , VAIKUNTANATHAN V . Trapdoors for hard lattices and new cryptographic constructions[A]. Proceedings of the 40th Annual ACM Symposium on Theory of Computing[C]. ACM, 2008. 197-206.
[10]	BOYEN X . Lattice mixing and vanishing trapdoors:a framework for fully secure short signatures and more[A]. Public Key Cryptography–PKC 2010[C]. Springer Berlin Heidelberg, 2010. 499-517.
[11]	CASH D , HOFHEINZ D , KILTZ E , et al. Bonsai trees,or how to delegate a lattice basis[J]. Journal of Cryptology, 2012,25(4): 601-639.
[12]	AGRAWAL S , BONEH D , BOYEN X . Efficient Lattice (H) IBE in the Standard Model[M]. Advances in Cryptology–EUROCRYPT 2010. Springer Berlin Heidelberg, 2010: 553-572.
[13]	BRAKERSKI Z , VAIKUNTANATHAN V . Efficient fully homomorphic encryption from (standard) LWE[A]. Foundations of Computer Science (FOCS),2011 IEEE 52nd Annual Symposium on[C]. IEEE, 2011. 97-106.
[14]	BRAKERSKI Z , GENTRY C , VAIKUNTANATHAN V . (Leveled) Fully homomorphic encryption without bootstrapping[A]. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference[C]. ACM, 2012. 309-325.
[15]	LEURENT Z , NGUYEN P . How risky is the random-oracle model[A]. Advances in Cryptology-CRYPTO 2009[C]. Springer Berlin Heidelberg, 2009. 445-464.
[16]	Lyubashevsky V . Lattice signatures without trapdoors[A]. Advances in Cryptology EUROCRYPT 2012[C]. Springer Berlin Heidelberg, 2012. 738-755.
[17]	DUCAS L , DURMUS A , LEPOINT T , et al. Lattice signatures and bimodal Gaussians[A]. Advances in Cryptology–CRYPTO 2013[C]. Springer Berlin Heidelberg, 2013. 40-56.
[18]	RüCKERT M . Strongly unforgeable signatures and hierarchical identitybased signatures from lattices without random oracles[A]. Post-Quantum Cryptography[C]. Springer Berlin Heidelberg, 2010. 182-200.
[19]	XIA F , YANG B , SUN W . An efficient identity-based signature from lattice in the random oracle model[J]. Journal of Computational Information Systems, 2011,7(11): 3963-3971.
[20]	TIAN M , HUANG L . Efficient identity-based signature from lattices[A]. ICT Systems Security and Privacy Protection[C]. Springer Berlin Heidelberg, 2014. 321-329.
[21]	TIAN M , HUANG L , YANG W . A new hierarchical identity-based signature scheme from lattices in the standard model[J]. IJ Network Security, 2012,14(6): 310-315.
[22]	LIU Z , HU Y , ZHANG X , et al. Efficient and strongly unforgeable identity-based signature scheme from lattices in the standard model[J]. Security and Communication Networks, 2013,6(1): 69-77.
[23]	MICCIANCIO D , GOLDWASSER S . Complexity of Lattice Problems:a Cryptographic Perspective[M]. Springer, 2002.
[24]	MICCIANCIO D , REGEV O . Worst-case to average-case reductions based on Gaussian measures[J]. SIAM Journal on Computing, 2007,37(1): 267-302.
[25]	ALWEN J , PEIKERT C . Generating shorter bases for hard random lattices[J]. Theory of Computing Systems, 2011,48(3): 535-553.

方案	公开参数大小	签名密钥长度	签名长度	安全模型	安全性
文献[ 18 ]方案	nm log q	3mlog q	3mlog q	ROM	SU
文献[ 20 ]方案	nm log q	mk log q	m log(12σ)	ROM	EU
文献[ 19 ]方案	nm log q	(m 1)log+ q	(m 1)log+ q	ROM	SU
文献[ 22 ]方案	(5m+1)nlogq	4m²log q	3mlog q	SM
改进后本方案	((d+4)m+1)n log q	4m²log q	3mlog q	SM	SU
注：这里的大小和长度都以bit为单位。其中n,m,q都是系统参数，表达的意义一样。且m?k,σ?q,d 表示消息压缩后的长度，其值为160～256。ROM表示随机预言机模型，SM表示标准模型，EU表示存在性不可伪造性，SU表示强不可伪造性。

对一个格基身份签名方案的分析和改进

Analysis and improvement of an identity-based signature scheme from lattices

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 25

相关文章 15

Metrics

推荐阅读 0

[1]	陈晓玉, 孙连峰, 张钇涵. 具有大零相关区宽度的Ⅱ型偶长Z-互补对构造方法[J]. 通信学报, 2023, 44(6): 167-174.
[2]	廉欢欢, 侯慧莹, 赵运磊. 后量子基于验证元的三方口令认证密钥交换协议[J]. 通信学报, 2022, 43(4): 95-106.
[3]	曹阳, 钟烨, 彭醇陵, 彭小峰. 基于混合供能和能量协作的异构网络能量效率优化算法[J]. 通信学报, 2022, 43(3): 135-147.
[4]	毛伊敏, 甘德瑾, 廖列法, 陈志刚. 基于Spark框架和ASPSO的并行划分聚类算法[J]. 通信学报, 2022, 43(3): 148-163.
[5]	郭渊博, 尹安琪. 基于格的口令认证密钥交换协议综述[J]. 通信学报, 2022, 43(12): 172-187.
[6]	郭红伟, 朱策, 杨栩, 罗雷. 基于失真反向传播的时域依赖率失真优化[J]. 通信学报, 2022, 43(12): 222-232.
[7]	董有恒, 赵耿, 马英杰. 基于分区初等元胞自动机的二维伪随机耦合映像格系统及其动态特性[J]. 通信学报, 2022, 43(1): 71-82.
[8]	侯红霞, 张明瑞, 赵艳琦, 董晓丽. 素数阶群上基于非对称对的身份基环签名[J]. 通信学报, 2021, 42(9): 155-164.
[9]	杨冬梅, 陈越, 魏江宏, 胡学先. 基于身份的可穿刺签名方案[J]. 通信学报, 2021, 42(12): 17-26.
[10]	田苗苗, 陈静, 仲红. 格上基于身份的增量签名方案[J]. 通信学报, 2021, 42(1): 108-117.
[11]	王宏禹,邱天爽. 特征算子谱表示与特征展开的研究[J]. 通信学报, 2020, 41(5): 1-8.
[12]	房礼国,付正欣,胡浩,沈刚,郁滨. 基于区域递增式彩色视觉密码的栅格地图多级分存算法研究[J]. 通信学报, 2019, 40(9): 24-32.
[13]	王天荆,李秀琴,白光伟,沈航. 无线传感器网络中基于自适应网格的多目标定位算法[J]. 通信学报, 2019, 40(7): 197-207.
[14]	杨小东,李雨潼,王晋利,麻婷春,王彩芬. 标准模型下可撤销的基于身份的代理重签名方案[J]. 通信学报, 2019, 40(5): 153-162.
[15]	田苗苗,高闯,陈洁. 格上基于身份的云存储完整性检测方案[J]. 通信学报, 2019, 40(4): 128-139.