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

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

通信学报 ›› 2021, Vol. 42 ›› Issue (1): 108-117.doi: 10.11959/j.issn.1000-436x.2021037

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

田苗苗, 陈静, 仲红

安徽大学计算机科学与技术学院，安徽合肥 230601

修回日期:2020-10-26 出版日期:2021-01-25 发布日期:2021-01-01
作者简介:田苗苗（1987- ），男，安徽阜阳人，博士，安徽大学副教授、硕士生导师，主要研究方向为密码学与信息安全。
陈静（1996- ），女，安徽池州人，安徽大学硕士生，主要研究方向为密码学与信息安全。
仲红（1965- ），女，安徽固镇人，博士，安徽大学教授、博士生导师，主要研究方向为网络与信息安全。
基金资助:
国家自然科学基金资助项目(61502443)

Identity-based incremental signature scheme from lattices

Miaomiao TIAN, Jing CHEN, Hong ZHONG

School of Computer Science and Technology, Anhui University, Hefei 230601, China

Revised:2020-10-26 Online:2021-01-25 Published:2021-01-01
Supported by:
The National Natural Science Foundation of China(61502443)

摘要/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

中图分类号:

TP309

田苗苗, 陈静, 仲红. 格上基于身份的增量签名方案[J]. 通信学报, 2021, 42(1): 108-117.

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

图/表 6

表1

表2

表3

实验参数的具体设置"

符号		值
符号	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 ⁶

表3

图1

图2

表4

参考文献 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.

方案	基于身份	标准模型	困难假设	适应性安全
文献[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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 27

相关文章 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]. 通信学报, 2020, 41(5): 1-8.
[10]	房礼国,付正欣,胡浩,沈刚,郁滨. 基于区域递增式彩色视觉密码的栅格地图多级分存算法研究[J]. 通信学报, 2019, 40(9): 24-32.
[11]	王天荆,李秀琴,白光伟,沈航. 无线传感器网络中基于自适应网格的多目标定位算法[J]. 通信学报, 2019, 40(7): 197-207.
[12]	杨小东,李雨潼,王晋利,麻婷春,王彩芬. 标准模型下可撤销的基于身份的代理重签名方案[J]. 通信学报, 2019, 40(5): 153-162.
[13]	田苗苗,高闯,陈洁. 格上基于身份的云存储完整性检测方案[J]. 通信学报, 2019, 40(4): 128-139.
[14]	曾锋,王润华,彭佳,陈志刚. 口碑参与模式下移动众包网络的用户博弈研究[J]. 通信学报, 2019, 40(3): 125-138.
[15]	赵耿,马艳艳,马英杰. 基于混沌序列的SCMA码本设计及系统性能分析[J]. 通信学报, 2019, 40(2): 137-144.