格上基于身份的增量签名方案

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

Abstract

Abstract:

By taking ideas of identity-based cryptography into incremental signatures, the concept of identity-based incremental signature was proposed, and then a specific scheme from lattices was also constructed.The scheme was shown to be provably secure against adaptive chosen identity and chosen message attacks in the standard model, assuming the hardness of the small integer solution problem.Theoretical analysis and experimental results show that the computational overhead of the incremental signature algorithm is less than that of the standard signature algorithm.

Key words: incremental signature, identity-based cryptography, lattice, standard model, small integer solution problem

CLC Number:

TP309

Miaomiao TIAN, Jing CHEN, Hong ZHONG. Identity-based incremental signature scheme from lattices[J]. Journal on Communications, 2021, 42(1): 108-117.

Figures/Tables 6

符号		值
符号	n=128		n=256
q	≈2 ⁵⁶		≈2 ⁶¹
β	≈9×10¹⁴		≈2×10¹⁶
$s_{1} (R)$	≈ 211		≈ 312
s	≈ 2 454		≈ 3 663
$s_{1} (R_{i d})$	≈10 ⁵		≈3×10 ⁵
$\tilde{s}$	≈2×10 ⁶		≈4×10 ⁶

References 27

[1]	GOLDWASSER S , MICALI S , RIVEST R . A digital signature scheme secure against adaptive chosen-message attacks[J]. SIAM Journal on computing, 1988,17(2): 281-308.
[2]	KHATI L , VERGNAUD D . Analysis and improvement of an authentication scheme in incremental cryptography[C]// International Conference on Selected Areas in Cryptography. Berlin:Springer, 2018: 50-70.
[3]	BELLARE M , GOLDREICH O , GOLDWASSER S . Incremental cryptography:the case of hashing and signing[C]// Annual International Cryptology Conference. Berlin:Springer, 1994: 216-233.
[4]	邵奇峰, 金澈清, 张召 ,等. 区块链技术:架构及进展[J]. 计算机学报, 2018,41(5): 969-988.
	SHAO Q F , JIN C Q , ZHANG Z ,et al. Blockchain:architecture and research progress[J]. Chinese Journal of Computers, 2018,41(5): 969-988.
[5]	ATIGHEHCHI K , . On the incremental digital signatures[C]// IEEE International Conference on Trust,Security and Privacy in Computing and Communications/IEEE International Conference on Big Data Science and Engineering (TrustCom/BigDataSE). Piscataway:IEEE Press, 2018: 1605-1609.
[6]	CHEN J , TIAN M , GAO C ,et al. A lattice-based incremental signature scheme[J]. IEEE Access, 2019,7: 21201-21210.
[7]	SHAMIR A , . Identity-based cryptosystems and signature schemes[C]// Workshop on the Theory and Application of Cryptographic Techniques. Berlin:Springer, 1984: 47-53.
[8]	AJTAI M , . Generating hard instances of lattice problems[C]// ACM Symposium on Theory of Computing. New York:ACM Press, 1996: 99-108.
[9]	MICCIANCIO D , REGEV O . Worst-case to average-case reductions based on Gaussian measures[J]. SIAM Journal on Computing, 2007,37(1): 267-302.
[10]	REGEV O , . Lattice-based cryptography[C]// Annual International Cryptology Conference. Berlin:Springer, 2006: 131-141.
[11]	TIAN M , HUANG L , WEI Y . A new hierarchical identity-based signature scheme from lattices in the standard model[J]. International Journal of Network Security, 2012,14(6): 310-315.
[12]	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.
[13]	TIAN M , HUANG L . Efficient identity-based signature from lattices[C]// IFIP International Information Security Conference. Berlin:Springer, 2014: 321-329.
[14]	TIAN M , HUANG L . Identity-based signatures from lattices:simpler,faster,shorter[J]. Fundamenta Informaticae, 2016,145(2): 171-187.
[15]	YANG Z , DUONG D ,et al. Hierarchical identity-based signature in polynomial rings[J]. The Computer Journal, 2020,63(10): 1490-1499.
[16]	XIE J , HU Y , GAO J ,et al. Efficient identity-based signature over NTRU lattice[J]. Frontiers of Information Technology ＆ Electronic Engineering, 2016,17(2): 135-142.
[17]	ZHAO G , TIAN M . A simpler construction of identity-based ring signatures from lattices[C]// International Conference on Provable Security. Berlin:Springer, 2018: 277-291.
[18]	孙意如, 梁向前, 商玉芳 . 理想格上基于身份的环签名方案[J]. 计算机应用, 2016,36(7): 1861-1865.
	SUN Y R , LIANG X Q , SHANG Y F . Identity based ring signature scheme in ideal lattice[J]. Journal of Computer Applications, 2016,36(7): 1861-1865.
[19]	CANETTI R , GOLDREICH O , HALEVI S . The random oracle methodology,revisited[J]. Journal of the ACM, 2004,51(4): 557-594.
[20]	ZHANG J , CHEN Y , ZHANG Z . Programmable hash functions from lattices:short signatures and IBEs with small key sizes[C]// Annual International Cryptology Conference. Berlin:Springer, 2016: 303-332.
[21]	MICCIANCIO D , PEIKERT C . Trapdoors for lattices:simpler,tighter,faster,smaller[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2012: 700-718.
[22]	BOYEN X , . Lattice mixing and vanishing trapdoors:a framework for fully secure short signatures and more[C]// International Workshop on Public Key Cryptography. Berlin:Springer, 2010: 499-517.
[23]	CHOON J , CHEON J . An identity-based signature from gap Diffie-Hellman groups[C]// International Workshop on Public Key Cryptography. Berlin:Springer, 2003: 18-30.
[24]	REGEV O , . On lattices,learning with errors,random linear codes,and cryptography[C]// ACM Symposium on Theory of Computing. New York:ACM Press, 2005: 84-93.
[25]	GENTRY C , PEIKERT C , VAIKUNTANATHAN V . Trapdoors for hard lattices and new cryptographic constructions[C]// ACM Symposium on Theory of Computing. New York:ACM Press, 2008: 197-206.
[26]	HOFHEINZ D , KILTZ E . Programmable hash functions and their applications[C]// Annual International Cryptology Conference. Berlin:Springer, 2008: 21-38.
[27]	BONEH D , FREEMAN D . Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures[C]// International Workshop on Public Key Cryptography. Berlin:Springer, 2011: 1-16.

Metrics

Recommended 0

No Suggested Reading articles found!

方案	基于身份	标准模型	困难假设	适应性安全
文献[3]方案	否	否	DL	是
文献[6]方案	否	是	k-SIS	是
本文方案	是	是	SIS	是

方案	公开参数大小	签名密钥大小	签名长度	标准模型	适应性安全
文献[11]方案	O(n ²t²)	O(n²t²)	O (nt)	是	否
文献[12]方案	O(n²t)	O(n²t²)	O (nt)	是	否
文献[13-14]方案	O(n²t)	O(n ²t)	O (nt)	否	是
文献[15]方案	O(n²t)	O(n²t²)	O(n²t)	否	否
本文方案	O(n²t)	O(n²t²)	O(n²t)	是	是

消息长度/bit	计算时间/s
消息长度/bit	n=128	n=256
256	0.96	3.86
384	1.42	6.22
512	2.18	8.81

Identity-based incremental signature scheme from lattices

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 27

Related Articles 15

Metrics

Recommended 0

[1]	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.
[2]	Yuanbo GUO, Anqi YIN. Research on password-authenticated key exchange protocol over lattices [J]. Journal on Communications, 2022, 43(12): 172-187.
[3]	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.
[4]	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.
[5]	Xiaodong YANG,Yutong LI,Jinli WANG,Tingchun MA,Caifen WANG. Revocable identity-based proxy re-signature scheme in the standard model [J]. Journal on Communications, 2019, 40(5): 153-162.
[6]	Miaomiao TIAN,Chuang GAO,Jie CHEN. Identity-based cloud storage integrity checking from lattices [J]. Journal on Communications, 2019, 40(4): 128-139.
[7]	Yatao YANG,Xinguang HAN,Jierun HUANG,Yang ZHAO. Bidirectional authentication key agreement protocol supporting identity’s privacy preservation based on RLWE [J]. Journal on Communications, 2019, 40(11): 180-186.
[8]	Qian MENG,Jianfeng MA,Kefei CHEN,Yinbin MIAO,Tengfei YANG. Data comparable encryption scheme based on cloud computing in Internet of things [J]. Journal on Communications, 2018, 39(4): 167-175.
[9]	Xixi YAN,Yuan LIU,Zichen LI,Yongli TANG,Qing YE. Privacy-preserving attribute-based encryption scheme on ideal lattices [J]. Journal on Communications, 2018, 39(3): 128-135.
[10]	Caifen WANG,Li CHEN. Three-party password authenticated key agreement protocol with user anonymity based on lattice [J]. Journal on Communications, 2018, 39(2): 21-30.
[11]	Xiaodong YANG,Chunlin CHEN,Ping YANG,Faying AN,Tingchun MA,Caifen WANG. Partially blind proxy re-signature scheme with proven security [J]. Journal on Communications, 2018, 39(2): 65-72.
[12]	Shao-bo YU,Ling-da WU,Xi-tao ZHANG. Research on space information representation model based on formal concept analysis [J]. Journal on Communications, 2017, 38(Z2): 78-85.
[13]	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.
[14]	Shu-fen NIU,Ling NIU,Cai-fen WANG,Ya-hong LI. Certificateless generalized signcryption scheme in the standard model [J]. Journal on Communications, 2017, 38(4): 35-45.
[15]	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.