Identity-based ring signatures from RSA

Shamir proposed in 1984 the first identity-based signature scheme, whose security relies on the RSA problem. A similar scheme was proposed by Guillou and Quisquater in 1988. Formal security of these schemes was not argued and/or proved until many years later [D. Pointcheval, J. Stern, Security arguments for digital signatures and blind signatures, Journal of Cryptology 13 (3) (2000) 361–396; Y. Dodis, J. Katz, S. Xu, M. Yung, Strong key-insulated signature schemes, in: Proceedings of PKC’03, in: LNCS, vol. 2567, Springer-Verlag, 2002, pp. 130–144; M. Bellare, C. Namprempre, G. Neven, Security proofs for identity-based identification and signature schemes, in: Proceedings of Eurocrypt’04, in: LNCS, vol. 3027, Springer-Verlag, 2004, pp. 268–286].Taking the Guillou–Quisquater scheme as the starting point, we design and analyze in this work ring signature schemes and distributed ring signature schemes for identity-based scenarios whose security is based on the hardness of the RSA problem. These are the first identity-based ring signature schemes which do not employ bilinear pairings. Furthermore, the resulting schemes satisfy an interesting property: the real author(s) of a ring signature can later open the anonymity and prove that he is actually the person who signed the message.