Accountable-subgroup multisignatures

Formal models and security proofs are especially important for multisignatures: in contrast to threshold signatures, no precise definitions were ever provided for such schemes, and some proposals were subsequently broken.In this paper, we formalize and implement a variant of multi-signature schemes, Accountable-Subgroup Multisignatures (ASM). In essence, ASM schemes enable any subgroup, S, of a given group, G, of potential signers, to sign efficiently a message M so that the signature provably reveals the identities of the signers in S to any verifier.Specifically, we provide:The first formal model of security for multisignature schemes that explicitly includes key generation (without relying on trusted third parties);A protocol, based on Schnorr's signature scheme 33, that is both provable and efficient:Only three rounds of communication are required per signature.The signing time per signer is the same as for the single-signer Schnorr scheme, regardless of the number of signers.The verification time is only slightly greater than that for the single-signer Schnorr scheme.The signature length is the same as for the single signer Schnorr scheme, regardless of the number of signers.Our proof of security relies on random oracles and the hardness of the Discrete Log Problem.