Cryptology ePrint Archive: Report 2009/240

Group Testing and Batch Verification

Gregory M. Zaverucha and Douglas R. Stinson

Abstract: We observe that finding invalid signatures in batches of signatures that fail batch verification is an instance of the classical group testing problem. We present and compare new sequential and parallel algorithms for finding invalid signatures based on group testing algorithms. Of the five new algorithms, three show improved performance for many parameter choices, and the performance gains are especially notable when multiple processors are available.

Category / Keywords: public-key cryptography / batch verification, group testing, digital signatures

Date: received 27 May 2009

Contact author: gzaveruc at cs uwaterloo ca

Available format(s): PDF | BibTeX Citation

Version: 20090530:123542 (All versions of this report)

Short URL: ia.cr/2009/240

Discussion forum: Show discussion | Start new discussion