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.
Category / Keywords: public-key cryptography / aggregate signatures, RSA, lazy verification, BGP Publication Info: This is the full version of the Asiacrypt 2012 paper Date: received 6 May 2011, last revised 25 Feb 2013 Contact author: reyzin at cs bu edu Available formats: PDF | BibTeX Citation Note: Project website with code: http://www.cs.bu.edu/~goldbe/papers/bgpsec-sigs.html Version: 20130225:193449 (All versions of this report) Discussion forum: Show discussion | Start new discussion