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

• Special Section on Selected Paper from NPC 2011 • 上一篇    下一篇


Adrian Atanasiu   

  • 收稿日期:2012-03-12 修回日期:2012-09-03 出版日期:2013-01-05 发布日期:2013-01-05

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


Abstract: 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] 刘明业; 洪恩宇;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] 王选; 吕之敏; 汤玉海; 向阳;. A High Resolution Chinese Character Generator[J]. , 1986, 1(2): 1 -14 .
[3] 陈世华;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[4] 高庆狮; 张祥; 杨树范; 陈树清;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[5] 章萃; 赵沁平; 徐家福;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[6] 陈肇雄; 高庆狮;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[7] 黄河燕;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[8] 闵应骅; 韩智德;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[9] 卢学妙;. On the Complexity of Induction of Structural Descriptions[J]. , 1987, 2(1): 12 -21 .
[10] 唐同诰; 招兆铿;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn