›› 2013, Vol. 28 ›› Issue (1): 144-151.doi: 10.1007/s11390-013-1318-4

• Information Security • Previous Articles     Next Articles

A New Batch Verifying Scheme for Identifying Illegal Signatures

Adrian Atanasiu   

  1. Faculty of Mathematics and Computer Science, Bucharest University, Str. Academiei 14, Bucharest 010014, Romania
  • Received:2012-03-12 Revised:2012-09-03 Online:2013-01-05 Published:2013-01-05

The concept of batch verifying multiple digital signatures is to find a method by which multiple digital signatures can be verified simultaneously in a lower time complexity than separately verifying all the signatures. In this article, we analyze the complexity of the batch verifying schemes defined by Li, Hwang and Chen in 2010, and propose a new batch verifying multiple digital signature scheme, in two variants: one for RSA - by completing the Harn’s schema with an identifying illegal signatures algorithm, and the other adapted for a modified Elliptic Curve Digital Signature Algorithm protocol.

[1] Bellare M, Garay J A, Rabin T. Fast batch verification formodular exponentiation and digital signatures. In LectureNotes in Computer Science 1403, Nyberg K (ed.), Springer-Verlag, 1998, pp.236-250.
[2] Boyd C, Pavlovski C. Attacking and repairing batch verificationschemes. In Proc. the 6th ASIACRYPT, Dec. 1976,pp.58-71.
[3] Camenish J, Hohenberger S, Pedersen M. Batch verificationof short signatures. In Proc. the 26th EUROCRYPT, May2007, pp.246-263.
[4] Hwang M, Lee C, Tang Y. Two simple batch verifying multipledigital signatures. In Proc. the 3rd ICICS, Nov. 2001,pp.233-237.
[5] Lim C H. Efficient multi-exponentation and applicationto batch verification of digital signatures. 2000,http://dasan.sejong.ac.kr/~chlim/pub/multi exp.ps.
[6] Kim K, Yie I, Lim S, Park H. A method of finding bad signaturesin an RSA-type batch verification. Informatica, 2011,22(2): 189-201.
[7] Kirn K, Yie I, Lim S, Nyang D. Batch verification and findinginvalid signatures in a group signature scheme. InternationalJournal of Network Security, 2011, 13(2): 61-70.
[8] Lee S, Cho S, Choi J, Cho Y. Efficient identification of bad signaturesin RSA-type batch signature. IEICE Trans. Fundamentalsof Electronics, Communications and Computer Sciences,2006, E89-A(1): 74-80.
[9] Matt B. Identification of multiple invalid signatures inpairing-based batched signatures. In Proc. the 12th Int.Conf. Practice and Theory in Public Key Cryptography,March 2009, pp.337-356.
[10] Bao F, Lee C, Hwang M. Cryptanalysis and improvementon batch verifying multiple RSA digital signatures. AppliedMathematics and Computation, 2006, 172(2): 1195-1200.
[11] Cao T, Lin D, Xue R. Security analysis of some batch verifyingsignatures from pairings. International Journal of NetworkSecurity, 2006, 3(2): 138-143.
[12] Hwang M, Lin I, Hwang K. Cryptanalysis of the batch verifyingmultiple RSA digital signatures. Informatica (LithuanianAcademy of Sciences), 2000, 11(1): 15-19.
[13] Lim C, Lee P. Security of interactive DSA batch verification.Electronics Letters, 1994, 30(19): 1592-1593.
[14] Selvi S S D, Vivek S S, Shriram J et al. Securityanalysis of aggregate signature and batch verification signatureschemes. IACR Crptology ePrint Archive, 2009,http://eprint.iacr.org/2009/290.pdf.
[15] Stanek M. Attacking LCCC batch verification of RSAsignatures. IACR Cryptology ePrint Archive, 2006,http://eprint.iacr.org/2006/111.pdf.
[16] Ferrara A, Green M, Hohenberger S, Pedersen M.On the practicality of short signature batch verification.IACR Cryptology ePrint Archive, 2008,http://eprint.iacr.org/2008/015.pdf.
[17] Cheon J H, Kim Y, Yoon H J. A new ID-based signaturewith batch verification. Cryptology ePrint Archive, 2004,http://eprint.iacr.org/2004/131.pdf.
[18] Cui S, Duan P, Chan C W. An efficient identity-based signaturescheme with batch verifications. In Proc. the 1st InfoScale,May 29-June 1, 2006, Article No.22.
[19] Yoon H, Cheon J H, Kim Y. Batch verifications with ID-basedsignatures. In Proc. the 7th ICISC, Dec. 2004, pp.233-248.
[20] Tzeng S, Lee C, Hwang M. A batch verification for multipleproxy signature. Parallel Processing Letters, 2011, 21(1):77-84.
[21] Zhang C, Ho P, Tapolcai J. On batch verification with grouptesting for vehicular communications. Wireless Network,2011, 17(8): 1851-1865.
[22] Changchien S W, Hwang M. A batch verifying and detectingmultiple RSA digital signatures. International Journalof Computational and Numerical Analysis and Applications,2002, 2(3): 303-307.
[23] Fiat A. Batch RSA. In Proc. the 9th CRYPTO, August 1989,pp.175-185.
[24] Harn L. Batch verifying multiple RSA digital signatures.Electronics Letters, 1998, 34(12): 1219-1220.
[25] Harn L. Batch verifying multiple DSA digital signatures.Electronics Letters, 1998, 34(9): 870-871.
[26] Li C, Hwang M, Chen S. A batch verifying and detecting theillegal signatures. International Journal of Innovative Computing,Information and Control, 2010, 6(12): 5311-5320.
[27] Stinton D. Cryptography Theory and Practice (2nd edition).Chapman & Hall/CRC, 2002.
[28] Cohen H, Frey G. Handbook of Elliptic and HyperellipticCurve Cryptography (Discrete Mathematics and Its Applications).Chapman & Hall/CRC, 2005.
[29] Hankerson D, Menezes A, Vanstome S. Guide to EllipticCurve Criptography. Springer Verlag, 2004.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Wang Xuan; Lü Zhimin; Tang Yuhai; Xiang Yang;. A High Resolution Chinese Character Generator[J]. , 1986, 1(2): 1 -14 .
[3] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[4] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[5] Zhang Cui; Zhao Qinping; Xu Jiafu;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[6] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[7] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[8] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[9] Lu Xuemiao;. On the Complexity of Induction of Structural Descriptions[J]. , 1987, 2(1): 12 -21 .
[10] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved