International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Transitive Signatures Based on Non-adaptive Standard Signatures

Zhou Sujing
Search ePrint
Search Google
Abstract: 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.
  title={Transitive Signatures Based on Non-adaptive Standard Signatures},
  booktitle={IACR Eprint archive},
  keywords={Signatures, Transitive signatures},
  note={No 12467 received 16 Feb 2004, last revised 18 Feb 2004},
  author={Zhou Sujing},