Group Testing and Batch Verification

Gregory M.  Zaverucha; Douglas R.  Stinson

Paper 2009/240 Original: eprint.iacr.org/2009/240 ↗

Group Testing and Batch Verification

Gregory M. Zaverucha

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: Preprint.
History: 2009-05-30: last updated; 2009-05-30: published
Short URL: https://ia.cr/2009/240
License: https://creativecommons.org/licenses/by/4.0/

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},
      url = {https://eprint.iacr.org/2009/240}
}