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$.
Category / Keywords: public-key cryptography / Pairing-based signatures, Batch verification, Invalid Signature Identification, Identitybased signatures, Short signatures, Wireless networks Publication Info: An abridged version of this paper appears in Pairing 2010 Date: received 28 Dec 2010 Contact author: brian j matt at gmail com Available formats: PDF | BibTeX Citation Version: 20101231:142420 (All versions of this report) Discussion forum: Show discussion | Start new discussion