International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Synchronized Aggregate Signatures: New Definitions, Constructions and Applications

Jae Hyun Ahn
Matthew Green
Susan Hohenberger
Search ePrint
Search Google
Abstract: An aggregate signature scheme is a digital signature scheme where anyone given n signatures on n messages from n users can aggregate all these signatures into a single short signature. Unfortunately, no ``fully non-interactive'' aggregate signature schemes are known outside of the random oracle heuristic; that is, signers must pass messages between themselves, sequentially or otherwise, to generate the signature. Interaction is too costly for some interesting applications. 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.
  title={Synchronized Aggregate Signatures: New Definitions, Constructions and Applications},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / signatures, aggregation},
  note={A preliminary version of this work will appear in ACM CCS 2010.   This is the full version. 14819 received 29 Jul 2010},
  author={Jae Hyun Ahn and Matthew Green and Susan Hohenberger},