### Identification of Multiple Invalid Pairing-based Signatures in Constrained Batches

Brian J. Matt

##### Abstract

This paper describes a new method in pairing-based signature schemes for identifying the invalid digital signatures in a batch after batch verification has failed. The method more efficiently identifies non-trivial numbers, $w$, of invalid signatures in constrained sized, $N$, batches than previously published methods, and does not require that the verifier possess detailed knowledge of $w$. Our method uses divide-and-conquer'' search to identify the invalid signatures within a batch, pruning the search tree to reduce the number of pairing computations required. The method prunes the search tree more rapidly than previously published techniques and thereby provides performance gains for batch sizes of interest. We are motivated by wireless systems where the verifier seeks to conserve computations or a related resource, such as energy, by using large batches. However, the batch size is constrained by how long the verifier can delay batch verification while accumulating signatures to verify. We compare the expected performance of our method (for a number of different signature schemes at varying security levels) for varying batch sizes and numbers of invalid signatures against earlier methods. We find that our new method provides the best performance for constrained batches, whenever the number of invalid signatures is less than half the batch size. We include recently published methods based on techniques from the group-testing literature in our analysis. Our new method consistently outperforms these group-testing based methods, and substantially reduces the cost ($> 50\%$) when $w \le N/4$.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. An abridged version of this paper appears in Pairing 2010
Keywords
Pairing-based signaturesBatch verificationInvalid Signature IdentificationIdentitybased signaturesShort signaturesWireless networks
Contact author(s)
brian j matt @ gmail com
History
Short URL
https://ia.cr/2010/660

CC BY

BibTeX

@misc{cryptoeprint:2010/660,
author = {Brian J.  Matt},
title = {Identification of Multiple Invalid Pairing-based Signatures in Constrained Batches},
howpublished = {Cryptology ePrint Archive, Paper 2010/660},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/660}},
url = {https://eprint.iacr.org/2010/660}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.