by Silvio Micali, Kazuo
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
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:
Our proof of security relies on random oracles and the
hardness of the Discrete Log Problem.
- 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
single-signer Schnorr scheme.
- The signature length is the same as for the single-signer
scheme, regardless of the number of signers.
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.