Accountable-Subgroup Multisignatures

by Silvio Micali, Kazuo Ohta and Leonid Reyzin

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:

  1. The first formal model of security for multisignature schemes that explicitly includes key generation (without relying on trusted third parties);
  2. A protocol, based on Schnorr's signature scheme [Sch91], that is both provable and efficient:
Our proof of security relies on random oracles and the hardness of the Discrete Log Problem.

An extended abstract of this work appears in CCS'01, Procedings of the Eighth ACM Conference on Computer and Communications Security, Pierangela Samarati, editor, pages 245-254, ©ACM 2001. Posted by permission of ACM.