Formal model of proxy multi-signature and a construction

As a variation of ordinary digital signature scheme, a proxy signature scheme enables a proxy signer to sign messages on behalf of the original signer. Proxy multi-signature is an extension of the basic proxy signature primitive, and permit two or more entities to delegate their signing capabilities to the same other entity. Although many proxy multi-signature schemes have been proposed since 2000, to date, no precise definitions or proofs of security have been provided for them. In this paper, the authors give the syntax of proxy multi-signature schemes and formalize a notion of security for them. The authors also construct a concrete scheme which is provably secure assuming the underlying groups are bilinear group pair and the computational Co-Diffie-Hellman problem is hard. Furthermore, the new scheme is very simple and has the property that the size of a proxy multi-signature is independent of the number of the original signers.