Transitive signatures: new schemes and proofs

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 (DH) groups. All these schemes are proven transitively unforgeable under adaptive chosen-message attack in the standard (not random-oracle) model. We also provide an answer to an open question raised by Micali and Rivest regarding the security of their Rivest-Shamir-Adleman (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.