Paper 2009/097

Identification of Multiple Invalid Signatures in Pairing-based Batched Signatures

Brian J. Matt

Abstract

This paper describes new methods in pairing-based signature schemes for identifying the invalid digital signatures in a batch, after batch verification has failed. These methods efficiently identify non-trivial numbers of invalid signatures in batches of (potentially large) numbers of signatures. Our methods use “divide-and-conquer” search to identify the invalid signatures within a batch, but prune the search tree to substantially reduce the number of pairing computations required. The methods presented in this paper require computing on average O(w) products of pairings to identify w invalid signatures within a batch of size N, compared with the O(w(log2(N/w)+1)) [for w < N/2] that traditional divide-and-conquer methods require. Our methods avoid the problem of exponential growth in expected computational cost that affect earlier proposals which, on average, require computing O(w) products of pairings. We compare the expected performance of our batch verification methods with previously published divide-and-conquer and exponential cost methods for Cha-Cheon identity-based signatures [6]. However, our methods also apply to a number of short signature schemes and as well as to other identity-based signature schemes.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. An abridged version of this paper appears in PKC 2009
Keywords
Pairing-based signaturesIdentity-based signaturesBatch verificationShort signaturesWireless networks
Contact author(s)
brian matt @ jhuapl edu
History
2009-03-02: received
Short URL
https://ia.cr/2009/097
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/097,
      author = {Brian J.  Matt},
      title = {Identification of Multiple Invalid Signatures in Pairing-based Batched Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/097},
      year = {2009},
      url = {https://eprint.iacr.org/2009/097}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.