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

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

Abstract

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

CLC Number:

TN918

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.

Figures/Tables 9

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

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

序号	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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 8

Related Articles 2

Metrics

Recommended 0

[1]	Hou-zhen WANG,Huan-guo ZHANG. Novel and lightweight digital signature scheme [J]. Journal on Communications, 2010, 31(11): 25-29.
[2]	Yan WO,Guo-qiang HAN,Jian-wei ZHANG,Bo ZHANG. New image content authentication algorithm based on wavelet transform and morphologic [J]. Journal on Communications, 2005, 26(8): 9-15.