Identity-Based Multi-signatures from RSA

Authors: M. Bellare and G. Neven

Abstract: Multi-signatures allow multiple signers to jointly authenticate a message using a single compact signature. Many applications however require the public keys of the signers to be sent along with the signature, partly defeating the effect of the compact signature. Since identity strings are likely to be much shorter than randomly generated public keys, the identity-based paradigm is particularly appealing for the case of multi-signatures. In this paper, we present and prove secure an identity-based multi-signature (IBMS) scheme based on RSA, which in particular does not rely on (the rather new and untested) assumptions related to bilinear maps. We define an appropriate security notion for interactive IBMS schemes and prove the security of our scheme under the one-wayness of RSA in the random oracle model.

Ref: Topics in Cryptology - CT-RSA 2007 Proceedings, Lecture Notes in Computer Science Vol. 4377, M. Abe ed, Springer-Verlag, 2007.

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