Efficient Identification of Bad Signatures in RSA-Type Batch Signature

Seungwon LEE  Seongje CHO  Jongmoo CHOI  Yookun CHO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.1   pp.74-80
Publication Date: 2006/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.1.74
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Digital Signature
batch verification,  batch identification,  RSA,  

Full Text: PDF(498.2KB)>>
Buy this Article

As the use of electronic voting systems and e-commerce systems increases, the efficient batch verification of digital signatures becomes more and more important. In this paper, we first propose a new method to identify bad signatures in batches efficiently for the case when the batch contains one bad signature. The method can find out the bad signature using smaller number of modular multiplications than the existing method. We also propose an extension to the proposed method to find out two or more bad signatures in a batch instance. Experimental results show that our method yields better performance than the existing method in terms of the number of modular multiplications.