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 . However, our methods also apply to a number of short signature schemes and as well as to other identity-based signature schemes.Category / Keywords: public-key cryptography / Pairing-based signatures, Identity-based signatures, Batch verification, Short signatures, Wireless networks Publication Info: An abridged version of this paper appears in PKC 2009 Date: received 26 Feb 2009, last revised 26 Feb 2009 Contact author: brian matt at jhuapl edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20090302:082956 (All versions of this report) Discussion forum: Show discussion | Start new discussion