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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
batch verificationgroup testingdigital signatures
Contact author(s)
gzaveruc @ cs uwaterloo ca
History
2009-05-30: received
Short URL
https://ia.cr/2009/240
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/240,
      author = {Gregory M.  Zaverucha and Douglas R.  Stinson},
      title = {Group Testing and Batch Verification},
      howpublished = {Cryptology ePrint Archive, Paper 2009/240},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/240}},
      url = {https://eprint.iacr.org/2009/240}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.