[Busec] Leo Reyzin at reading group tomorrow, 11AM MCS137

Sharon Goldberg goldbe at cs.bu.edu
Mon Mar 21 10:05:52 EDT 2011

Hi everyone,

Hope you had a good break! We resume reading group tomorrow with a
practice talk by Leo Reyzin on our new work on cryptographic aggregate
signatures.  Leo will be presenting this at MIT in a few weeks, so
we'd appreciate having your feedback tomorrow, 11AM in MCS137.

See you there,


Sequential Aggregate Signatures with Lazy Verification for S-BGP

Talk by Leo Reyzin (joint work with Sharon Goldberg and Kyle Brogle)

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 (such as RSA) that, unlike prior
such proposals, does not require a signer to verify the received
aggregate before adding a signature on a new message to it.  In fact,
a signer need not even know the public keys of the other signers.

Our scheme is especially designed for Secure BGP (S-BGP), a protocol
designed for securing the global Internet routing system.  With S-BGP,
routers digitally sign the routing announcements they forward to other
routers.  Because routing announcements are sent in a chain along a
route, aggregating multiple signatures to reduce the total signature
length is a natural way to reduce communication costs.  Practical
implementations of S-BGP must offer routers the option of performing
"lazy verification":  that is, to add their own signature to an
unverified aggregate and forward it immediately, postponing
verification until load permits or the necessary public keys are
obtained.  However, many prior schemes do not allow for lazy
verification; indeed, adding a signature to an unverified aggregate
breaks the security guarantees, and can lead to devastating attacks.
Our scheme explicitly allows for lazy verification.

We report a technical analysis of the scheme (which is provably secure
in the random oracle model), a detailed implementation-level
specification, and implementation results based on RSA and OpenSSL.
Our scheme has much shorter signatures than nonaggregate RSA (with the
same sign and verify times) and two orders of magnitude faster
verification than nonaggregate ECDSA, although ECDSA has shorter
signatures when the number of signers is small.

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list