Paper 2004/215

Transitive Signatures: New Schemes and Proofs

Mihir Bellare and Gregory Neven


We present novel realizations of the transitive signature primitive introduced by Micali and Rivest, enlarging the set of assumptions on which this primitive can be based, and also providing performance improvements over existing schemes. More specifically, we propose new schemes based on factoring, the hardness of the one-more discrete logarithm problem, and gap Diffie-Hellman groups. All these schemes are proven transitively unforgeable under adaptive chosen-message attack. We also provide an answer to an open question raised by Micali and Rivest regarding the security of their RSA-based scheme, showing that it is transitively unforgeable under adaptive chosen-message attack assuming the security of RSA under one-more-inversion. We then present hash-based modifications of the RSA, factoring and gap Diffie-Hellman based schemes that eliminate the need for ``node certificates'' and thereby yield shorter signatures. These modifications remain provably secure under the same assumptions as the starting scheme, in the random oracle model.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. An extended abstract of this paper appeared as "Transitive Signatures based on Factoring and RSA" in Asiacrypt 2002. This is a slightly revised version of the full paper that appeared in IEEE Transactions on Information Theory, Vol.51, No. 6, pp. 2133--2151, June 2005.
SignaturestransitiveRSAfactoringpairingsGap Diffie-Hellman
Contact author(s)
mihir @ cs ucsd edu
2005-08-31: last of 4 revisions
2004-08-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Gregory Neven},
      title = {Transitive Signatures: New Schemes and Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2004/215},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.