In this work, we present both theoretical and practical contributions. On the theoretical side, we introduce new batch verifiers for a wide variety of regular, identity-based, group, ring and aggregate signature schemes. These are the first constructions for batching group signatures, which answers an open problem of Camenisch et al. On the practical side, we implement each of these algorithms and compare each batching algorithm to doing individual verifications. Our goal is to test whether batching is practical; that is, whether the benefits of removing pairings significantly outweigh the cost of the additional operations required for batching, such as group membership testing, randomness generation, and additional modular exponentiations and multiplications. We experimentally verify that the theoretical results of Camenisch et al. and this work, indeed, provide an efficient, effective approach to verifying multiple signatures from (possibly) different signers.
Category / Keywords: implementation / signatures, batch verification Publication Info: Full version of the CT-RSA 2009 paper Date: received 9 Jan 2008, last revised 21 Jan 2009 Contact author: susan at cs jhu edu Available format(s): PDF | BibTeX Citation Version: 20090121:080223 (All versions of this report) Short URL: ia.cr/2008/015 Discussion forum: Show discussion | Start new discussion