基于正交拉丁方理论的数字签名分组批量验证

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

通信学报 ›› 2022, Vol. 43 ›› Issue (2): 44-54.doi: 10.11959/j.issn.1000-436x.2022036

基于正交拉丁方理论的数字签名分组批量验证

王宏¹, 赖成喆², 刘向阳¹, 曾晗¹

¹ 国防科技大学信息通信学院，陕西西安 710106
² 西安邮电大学网络空间安全学院，陕西西安 710121

修回日期:2022-01-18 出版日期:2022-02-25 发布日期:2022-02-01
作者简介:王宏（1979-），男，陕西澄城人，博士，国防科技大学讲师，主要研究方向为无线网络安全、有限域等
赖成喆（1985-），男，陕西汉中人，博士，西安邮电大学教授、硕士生导师，主要研究方向为无线网络安全
刘向阳（1976-），男，河南许昌人，博士，国防科技大学副教授、硕士生导师，主要研究方向为无线传感器网络、信号检测等
曾晗（1991-），女，河南南阳人，国防科技大学讲师，主要研究方向为无线网络安全
基金资助:
国家自然科学基金资助项目(61871471);陕西省重点研发计划基金资助项目(2021ZDLGY06-02)

Orthogonal Latin square theory based group and batch verification for digital signatures

Hong WANG¹, Chengzhe LAI², Xiangyang LIU¹, Han ZENG¹

¹ College of Information and Communication, National University of Defense Technology, Xi’an 710106, China
² School of Cyberspace Security, Xi’an University of Posts and Telecommunications, Xi’an 710121, China

Revised:2022-01-18 Online:2022-02-25 Published:2022-02-01
Supported by:
The National Natural Science Foundation of China(61871471);The Key Research and Development Program of Shaanxi Province(2021ZDLGY06-02)

摘要/Abstract

摘要：

针对态势感知网络中海量的、时敏性强的消息需要中心节点进行快速、安全验证的问题，基于组合数学的正交拉丁方理论设计了数字签名分组批量认证方案。该方案着眼于消息安全性验证效率的提升，利用正交拉丁方理论设计数字签名的分组方案，以聚合签名理论作为签名批量验证算法，构建了一个采取多个处理器并行运算的非适应性数字签名分组批量验证模型。理论证明和仿真分析表明，所提模型在非法数字签名个数上限d（ $d ≪ n$ ）已知的条件下，能以大约 $\sqrt{n}$ 次数完成 n 个非法数字签名的识别，特别是在多个处理器计算的情况下相比逐一验证、二分法验证具有时效高、容错性强的特点。

关键词: 数字签名, 正交拉丁方, 分组设计, 批量验证

Abstract:

In order to solve the problem of fast security verification of massive and time-intensive messages on a central node in situational awareness networks, orthogonal Latin square theory based scheme was considered.Considering efficiency promotion of security verification of messages, group design of digital signatures based on orthogonal Latin square theory was formulated, batch verification of digital signatures was processed by aggregate signature, then an efficient, parallel and non-adaptive batch verification scheme of digital signatures was proposed in according with multiple processors.Theoretical analysis and simulation results demonstrate that it will be able to identify n digital signatures by approximately $\sqrt{n}$ times given the upper bound d ( $d ≪ n$ ) of invalid digital signatures, together with higher time-efficiency and stronger error-tolerance by comparing with individual testing and binary splitting algorithms especially when multiple processors are available.

Key words: digital signatures, orthogonal Latin square, group design, batch verification

中图分类号:

TN918

王宏, 赖成喆, 刘向阳, 曾晗. 基于正交拉丁方理论的数字签名分组批量验证[J]. 通信学报, 2022, 43(2): 44-54.

Hong WANG, Chengzhe LAI, Xiangyang LIU, Han ZENG. Orthogonal Latin square theory based group and batch verification for digital signatures[J]. Journal on Communications, 2022, 43(2): 44-54.

图/表 9

图1

图2

图3

图4

图5

表1

图6

表2

数字签名分组检测比较"

算法	最大检测次数
算法	单个处理器	p个处理器
逐一验证	n	$⌈ \frac{n}{p} ⌉$
二分法验证	$d ⌈ \log n ⌉$	$d ⌈ \log \frac{n}{p} ⌉$
本文算法	$(d + 1) \sqrt{n}$	$\frac{(d + 1) \sqrt{n}}{p}$

表2

图7

参考文献 8

[8]	YANG T , KONG L B , HU J B ,et al. Survey on aggregate signature and its applications[J]. Journal of Computer Research and Development, 2012,49(S2): 192-199.
[9]	BONEH D , GENTRY C , LYNN B ,et al. Aggregate and verifiably encrypted signatures from bilinear maps[J]. IACR Cryptology ePrint Archive,2002, 2002:175.
[10]	HWANG J Y , LEE D H , YUNG M . Universal forgery of the identity-based sequential aggregate signature scheme[C]// Proceedings of the 4th International Symposium on Information,Computer,and Communications Security.[S.l.:s.n.], 2009: 157-160.
[11]	WEI X J , ZHANG L , LU D J . An aggregate signature scheme with forward security and non-repudiation[C]// Proceedings of the 2019 2nd International Conference on Information Hiding and Image Processing. New York:ACM Press, 2019: 15-20.
[12]	DU D Z , HWANG F K . Combinatorial group testing and its applications[M]. Singapore: World Scientific, 1993.
[13]	ZAVERUCHA G M , STINSON D R . Group testing and batch verification[J]. IACR Cryptology ePrint Archive,2009, 2009:240.
[14]	SCARLETT J , CEVHER V . Phase transitions in group testing[C]// Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia:Society for Industrial and Applied Mathematics, 2016: 40-53.
[15]	SHANGGUAN C , GE G N . New bounds on the number of tests for disjunct matrices[J]. IEEE Transactions on Information Theory, 2016,62(12): 7518-7521.
[16]	INDYK P , NGO H Q , RUDRA A . Efficiently decodable non-adaptive group testing[C]// Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia:Society for Industrial and Applied Mathematics, 2010: 1126-1142.
[17]	ISCEN A , FURON T . Group testing for identification with privacy[C]// Proceedings of the 4th ACM Workshop on Information Hiding and Multimedia Security. New York:ACM Press, 2016: 51-56.
[18]	CHERAGHCHI M , NAKOS V . Combinatorial group testing and sparse recovery schemes with near-optimal decoding time[C]// Proceedings of 2020 IEEE 61st Annual Symposium on Foundations of Computer Science. Piscataway:IEEE Press, 2020: 1203-1213.
[19]	BONEH D , GENTRY C , LYNN B ,et al. Aggregate and verifiably encrypted signatures from bilinear maps[C]// Advances in Cryptology— EUROCRYPT 2003.[S.l.:s.n.], 2003: 416-428.
[20]	BRUALDI R . Introductory combinatorics[M]. New Jersey: Prentice Hall, 2004.
[21]	PASTUSZAK J , PIEPRZYK J , SEBERRY J . Codes identifying bad signatures in batches[C]// Proceedings of 2000 International Conference on Cryptology in India (INDOCRYPT). Berlin:Springer, 2000: 143-154.
[22]	邵嘉裕 . 组合数学[M]. 上海: 同济大学出版社, 1991.
	SHAO J Y . Combinatorial mathematics[M]. Shanghai: Tongji University Press, 1991.
[1]	ZHANG C X , HO P H , TAPOLCAI J . On batch verification with group testing for vehicular communications[J]. Wireless Networks, 2011,17(8): 1851-1865.
[2]	WANG Y H , . A trust management model for Internet of vehicles[C]// Proceedings of the 2020 4th International Conference on Cryptography,Security and Privacy. New York:ACM Press, 2020: 136-140.
[3]	王宏, 李建华, 赖成喆 ,等. 基于纠错码理论的群组认证[J]. 电子学报, 2019,47(7): 1393-1400.
	WANG H , LI J H , LAI C Z ,et al. Group authentication based on error correction coding theory[J]. Acta Electronica Sinica, 2019,47(7): 1393-1400.
[4]	MAKAROV A . A survey of aggregate signature applications[J]. Advanced Technologies in Robotics and Intelligent Systems, 2020,80(1): 309-317.
[5]	KOZINA G L , SAVCHENKO D K . Aggregate signature protocol with group leader[J]. Cybernetics and Systems Analysis, 2021,57(1): 165-172.
[6]	TEZUKA M , TANAKA K . Improved security proof for the camenisch-lysyanskaya signature-based synchronized aggregate signature scheme[M]. Cham: Springer, 2020.
[7]	HE M , LI X M , NI J B ,et al. Balancing efficiency and security for network access control in space-air-ground integrated networks[C]// Proceedings of 2021 18th International Conference on Privacy,Security and Trust (PST). Piscataway:IEEE Press, 2021: 1-10.
[23]	WAN Z X . Finite fields and galois rings[M]. Singapore: World Scientific Publishing, 2011.
[8]	杨涛, 孔令波, 胡建斌 ,等. 聚合签名及其应用研究综述[J]. 计算机研究与发展, 2012,49(S2): 192-199.

序号	n	t	k	m	d	时间/s
1	49	21	3	7	2	1.886
2	361	76	4	19	3	4.166
3	961	155	5	31	4	9.420
4	1 849	301	7	43	6	21.988
5	4 096	640	10	64	9	36.560
6	4 489	737	11	67	10	39.211
7	4 489	1 541	23	67	22	90.660
8	4 489	2 077	31	67	30	132.267
9	4 489	3 149	47	67	46	198.886
10	4 489	3 685	55	67	54	223.980

基于正交拉丁方理论的数字签名分组批量验证

Orthogonal Latin square theory based group and batch verification for digital signatures

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 8

相关文章 15

Metrics

推荐阅读 0

[1]	张艳硕, 刘宁, 袁煜淇, 杨亚涛. 基于ISRSAC数字签名算法的适配器签名方案[J]. 通信学报, 2023, 44(3): 178-185.
[2]	薛一鸣, 刘树荣, 郭书恒, 李岩, 胡彩娥. 高速Ed25519验签算法硬件架构的设计与实现[J]. 通信学报, 2022, 43(3): 101-112.
[3]	史瑞, 封化民, 谢惠琴, 史国振, 刘飚, 杨旸. 基于带智能卡的移动终端实现的隐私保护的属性票据方案[J]. 通信学报, 2022, 43(10): 26-41.
[4]	贺蕾, 马建峰, 魏大卫. 面向无人机网络的属性代理签名方案[J]. 通信学报, 2021, 42(11): 87-96.
[5]	田传俊. 密钥非均匀分布的完善保密通信系统[J]. 通信学报, 2018, 39(11): 1-9.
[6]	朱兵,李挥,陈俊,侯韩旭,周泰. 基于可分组设计的部分重复码研究[J]. 通信学报, 2015, 36(2): 98-105.
[7]	古春生. 破解新型的轻量级数字签名方案[J]. 通信学报, 2013, 34(7): 154-158.
[8]	古春生1,2,3. 破解新型的轻量级数字签名方案[J]. 通信学报, 2013, 34(7): 17-158.
[9]	刘亚丽,秦小麟,殷新春,李博涵. 基于模m的n方根的前向安全数字签名方案的分析与改进[J]. 通信学报, 2010, 31(6): 82-88.
[10]	王后珍,张焕国. 新型的轻量级数字签名方案[J]. 通信学报, 2010, 31(11): 25-29.
[11]	王潮,时向勇,牛志华. 基于Montgomery曲线改进ECDSA算法的研究[J]. 通信学报, 2010, 31(1): 9-13.
[12]	王化群,徐名海,郭显久. 几种无证书数字签名方案的安全性分析及改进[J]. 通信学报, 2008, 29(5): 88-92.
[13]	叶登攀,尚月赟. 基于多特征的MPEG视频认证方案[J]. 通信学报, 2008, 29(2): 59-65.
[14]	李志敏,王励成,郑世慧,杨义先. 随机散列函数安全性与签名者作弊[J]. 通信学报, 2008, 29(10): 101-107.
[15]	张国印,王玲玲,马春光. 环签名研究进展[J]. 通信学报, 2007, 28(5): 109-117.