In this work, we consider the task of realizing aggregate signatures in the model of Gentry and Ramzan (PKC 2006) when all signers share a synchronized clock, but do not need to be aware of or interactive with one another. Each signer may issue at most one signature per time period and signatures aggregate only if they were created during the same time period. We call this synchronized aggregation.
We present a practical synchronized aggregate signature scheme secure under the Computational Diffie-Hellman assumption in the standard model. Our construction is based on the stateful signatures of Hohenberger and Waters (Eurocrypt 2009). Those signatures do not aggregate since each signature includes unique randomness for a chameleon hash and those random values do not compress. To overcome this challenge, we remove the chameleon hash from their scheme and find an alternative method for moving from weak to full security that enables aggregation. We conclude by discussing applications of this construction to sensor networks and software authentication.
Category / Keywords: public-key cryptography / signatures, aggregation Publication Info: A preliminary version of this work will appear in ACM CCS 2010. This is the full version. Date: received 29 Jul 2010 Contact author: susan at cs jhu edu Available format(s): PDF | BibTeX Citation Version: 20100730:035517 (All versions of this report) Short URL: ia.cr/2010/422