Paper 2012/562

Aggregating CL-Signatures Revisited: Extended Functionality and Better Efficiency

Kwangsu Lee, Dong Hoon Lee, and Moti Yung


Aggregate signature is public-key signature that allows anyone to aggregate different signatures generated by different signers on different messages into a short (called aggregate) signature. The notion has many applications where compressing the signature space is important: secure routing protocols, compressed certificate chain signature, software module authentications, and secure high-scale repositories and logs for financial transactions. In spite of its importance, the state of the art of the primitive is that it has not been easy to devise a suitable aggregate signature scheme that satisfies the conditions of real applications, with reasonable parameters: short public key size, short aggregate signatures size, and efficient aggregate signing/verification. In this paper, we propose aggregate signature schemes based on the Camenisch-Lysyanskaya (CL) signature scheme (Crypto 2004) whose security is reduced to that of CL signature which substantially improve efficiency conditions for real applications. - We first propose an efficient \textit{sequential aggregate signature} scheme with the shortest size public key, to date, and very efficient aggregate verification requiring only a constant number of pairing operations and $l$ number of exponentiations ($l$ being the number of signers). - Next, we propose an efficient \textit{synchronized aggregate signature} scheme with a very short public key size, and with the shortest (to date) size of aggregate signatures among synchronized aggregate signature schemes. Signing and aggregate verification are very efficient: they take constant number of pairing operations and $l$ number of exponentiations, as well. - Finally, we introduce a new notion of aggregate signature named \textit{combined aggregate signature} that allows a signer to dynamically use two modes of aggregation ``sequential'' and ``synchronized,'' employing the same private/public key. We also present an efficient combined aggregate signature based on our previous two aggregate signature schemes. This combined-mode scheme allows for application flexibility depending on real world scenario: For example, it can be used sequentially to sign incrementally generated legal documents, and synchronously to aggregate the end-of-day logs of all branches of an institute into a single location with a single aggregate signature.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.FC 2013
Public-key signatureAggregate signatureCL signature
Contact author(s)
guspin lee @ gmail com
2013-11-24: last of 2 revisions
2012-10-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kwangsu Lee and Dong Hoon Lee and Moti Yung},
      title = {Aggregating CL-Signatures Revisited: Extended Functionality and Better Efficiency},
      howpublished = {Cryptology ePrint Archive, Paper 2012/562},
      year = {2012},
      doi = {10.1007/978-3-642-39884-1_14},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.