2012 | OriginalPaper | Chapter
Sequential Aggregate Signatures with Lazy Verification from Trapdoor Permutations
(Extended Abstract)
Authors : Kyle Brogle, Sharon Goldberg, Leonid Reyzin
Published in: Advances in Cryptology – ASIACRYPT 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Sequential aggregate signature schemes allow
n
signers, in order, to sign a message each, at a lower total cost than the cost of
n
individual signatures. We present a sequential aggregate signature scheme based on trapdoor permutations (
e.g.
, RSA). Unlike prior such proposals, our scheme does not require a signer to retrieve the keys of other signers and verify the aggregate-so-far before adding its own signature. Indeed, we do not even require a signer to
know
the public keys of other signers!
Moreover, for applications that require signers to verify the aggregate anyway, our schemes support
lazy verification
: a signer can add its own signature to an unverified aggregate and forward it along immediately, postponing verification until load permits or the necessary public keys are obtained. This is especially important for applications where signers must access a large, secure, and current cache of public keys in order to verify messages. The price we pay is that our signature grows slightly with the number of signers.
We report a technical analysis of our scheme (which is provably secure in the random oracle model), a detailed implementation-level specification, and implementation results based on RSA and OpenSSL. To evaluate the performance of our scheme, we focus on the target application of BGPsec (formerly known as Secure BGP), a protocol designed for securing the global Internet routing system. There is a particular need for lazy verification with BGPsec, since it is run on routers that must process signatures extremely quickly, while being able to access tens of thousands of public keys. We compare our scheme to the algorithms currently proposed for use in BGPsec, and find that our signatures are considerably shorter nonaggregate RSA (with the same sign and verify times) and have an order of magnitude faster verification than nonaggregate ECDSA, although ECDSA has shorter signatures when the number of signers is small.