Accountable-Subgroup Multisignatures
by Silvio Micali, Kazuo
Ohta
and Leonid Reyzin
Abstract
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 [Sch91],
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.
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.