We build on this result to offer the first *identity-based* aggregate signature scheme that admits unrestricted aggregation. In our construction, an arbitrary-sized set of signatures on identity/message pairs can be aggregated into a single group element, which authenticates the entire set. The identity-based setting has important advantages over regular aggregate signatures in that it eliminates the considerable burden of having to store, retrieve or verify a set of verification keys, and minimizes the total cryptographic overhead that must be attached to a set of signer/message pairs. While identity-based signatures are trivial to achieve, their aggregate counterparts are not. To the best of our knowledge, no prior candidate for realizing unrestricted identity-based aggregate signatures exists in either the standard or random oracle models.
A key technical idea underlying these results is the realization of a hash function with a Naor-Reingold-type structure that is publicly computable using repeated application of the multilinear map. We present our results in a generic ``leveled'' multilinear map setting and then show how they can be translated to the GGH graded algebras analogue of multilinear maps.Category / Keywords: public-key cryptography / full domain hash, identity-based aggregate signatures, multilinear maps Publication Info: This is the full version of the paper in CRYPTO 2013. Date: received 9 Jul 2013, last revised 30 Jul 2013 Contact author: susan at cs jhu edu Available format(s): PDF | BibTeX Citation Version: 20130730:205113 (All versions of this report) Short URL: ia.cr/2013/434 Discussion forum: Show discussion | Start new discussion