Paper 2012/562

Aggregating CL-Signatures Revisited: Extended Functionality and Better Efficiency

Kwangsu Lee, Dong Hoon Lee, and Moti Yung

Abstract

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.