FSS2-Id/A Fast Safe Identity-Based Multi Signature Scheme

In this paper, an identity-based multi signature scheme (IBMS) is presented. Many applications require that public keys of the signers to be sent along the signature. Identity strings are likely to be much shorter than randomly generated public keys and are easily verifiable with other applications such as mail or web pages. This property makes the identity based paradigm appealing in such a situation. The new scheme is based on the difficulty of factoring a Rivest Adleman Shamir integer and in particular does not rely on the untested assumptions on bilinear maps. A proof of security for this IBMS is obtained under the assumption of the one wayness of the RSA in the random oracle model. It is analogous but not equivalent to the Bellare scheme. A modified version which uses less network resources and therefore adapted for a large number of signers, is also presented.