Multisignatures in the Plain Public-Key Model and a General Forking Lemma

Authors: M. Bellare and G. Neven

Abstract: A multi-signature scheme enables a group of signers to produce a compact, joint signature on a common document, and has many potential uses. However, existing schemes impose key setup or PKI requirements that make them impractical, such as requiring a dedicated, distributed key generation protocol amongst potential signers, or assuming strong, concurrent zero-knowledge proofs of knowledge of secret keys done to the CA at key registration. These requirements limit the use of the schemes. We provide a new scheme that is proven secure in the plain public-key model, meaning requires nothing more than that each signer has a (certified) public key. Furthermore the important simplification in key-management achieved is not at the cost of efficiency or assurance:~our scheme matches or surpasses known ones in terms of signing time, verification time and signature size, and is proven secure in the random-oracle model under a standard (not bilinear map related) assumption. The proof is based on a simplified and generalized Forking Lemma that may be of independent interest.

Ref: Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS), ACM, 2006.

Proceedings paper: Available as pdf. ( Help if this doesn't work).