Non-interactive multisignatures in the plain public-key model with efficient verification

Multisignatures extend standard digital signatures to allow an ad hoc set of users to jointly sign a message. Multisignature schemes are often evaluated from the following perspectives: (1) the cryptographic assumptions underlying the schemes; (2) the operational assumptions about the bootstrapping of the schemes in practice; (3) the number of communication rounds for signing a message; (4) the time complexity for signing a message; (5) the amount of communication for signing a message; (6) the time complexity for verifying a multisignature; (7) the length of the resulting multisignatures. Existing multisignature schemes achieve various trade-offs among these measures, but none of them can achieve simultaneously the desired properties with respect to all (or even most) of these measures. In this paper, we present a novel multisignature scheme that offers desired properties with respect to the above (1)-(7) simultaneously, except that it uses random oracles (which however are often required in order to design practical schemes). In particular, our scheme is featured by its weak operational (i.e., plain public-key) model, non-interactive signing, and efficient verification.