Paper 2004/044

Transitive Signatures Based on Non-adaptive Standard Signatures

Zhou Sujing


Transitive signature, motivated by signing vertices and edges of a dynamically growing, transitively closed graph, was first proposed by Micali and Rivest. The general designing paradigm proposed there involved a underlying standard signature scheme, which is required to be existentially unforgeable against adaptive chosen message attacks. We show that the requirement for the underlying signature is not necessarily so strong, instead non-adaptive security is enough to guarantee the transitive signature scheme secure in the strongest sense, i.e, transitively unforgeable under adaptive chosen message attack (defined by Bellare and Neven). We give a general proof of such transitive signature schemes, and also propose a specific transitive signature scheme based on factoring and strong-RSA. Hence the choice of standard signatures that can be employed by transitive signature schemes is enlarged. The efficiency of transitive signature schemes may be improved since efficiency and security are trade-off parameters for standard signature schemes.

Available format(s)
Publication info
Published elsewhere. No
SignaturesTransitive signatures
Contact author(s)
zhousujing @ yahoo com cn
2004-02-19: revised
2004-02-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zhou Sujing},
      title = {Transitive Signatures Based on Non-adaptive Standard Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2004/044},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.