CryptoDB
On the Practicality of Short Signature Batch Verification
| Authors: | |
|---|---|
| Download: | |
| Abstract: | As pervasive communication becomes a reality, where everything from vehicles to heart monitors constantly communicate with their environments, system designers are facing a cryptographic puzzle on how to authenticate messages. These scenarios require that : (1) cryptographic overhead remain short, and yet (2) many messages from many different signers be verified very quickly. Pairing-based signatures have property (1) but not (2), whereas schemes like RSA have property (2) but not (1). As a solution to this dilemma, Camenisch, Hohenberger and Pedersen showed how to batch verify two pairing-based signatures so that the total number of pairing operations was independent of the number of signatures to verify. CHP left open the task of batching privacy-friendly authentication, which is desirable in many pervasive communication scenarios. In this work, we revisit this issue from a more practical standpoint and present the following results: 1. We describe a framework, consisting of general techniques, to help scheme and system designers understand how to {\em securely} and {\em efficiently} batch the verification of pairing equations. 2. We present a detailed study of when and how our framework can be applied to existing regular, identity-based, group, ring, and aggregate signature schemes. To our knowledge, these batch verifiers for group and ring signatures are the first proposals for batching privacy-friendly authentication, answering an open problem of Camenisch et al. 3. While prior work gave mostly asymptotic efficiency comparisons, we show that our framework is practical by implementing our techniques and giving detailed performance measurements. Additionally, we discuss how to deal with invalid signatures in a batch and our empirical results show that when roughly less than 10% of signatures are invalid, batching remains more efficient that individual verification. Indeed, our results show that batch verification for short signatures is an effective, efficient approach. |
BibTeX
@misc{eprint-2008-17692,
title={On the Practicality of Short Signature Batch Verification},
booktitle={IACR Eprint archive},
keywords={implementation / signatures, batch verification},
url={http://eprint.iacr.org/2008/015},
note={ susan@cs.jhu.edu 13895 received 9 Jan 2008, last revised 17 Jan 2008},
author={Anna Lisa Ferrara and Matthew Green and Susan Hohenberger and Michael Ostergaard Pedersen},
year=2008
}