Transitive signatures based on factoring and RSA
and Gregory Neven. In Y. Zheng, editor, Advances in Cryptology -
ASIACRYPT 2002, volume 2501 of Lecture Notes in Computer Science,
pages 397-414. Springer-Verlag, 2002.
Abstract: We present novel realizations of the transitive signature primitive introduced by Micali and Rivest [MR02]. Our first scheme, FBTS-1, is proven transitively unforgeable under adaptive chosen-message attack assuming factoring is hard. We then present a hash-based modification, FBTS-2 achieving shorter signatures by eliminating the need for "node certificates", and provable under the same factoring assumption in the random oracle model. We also provide an answer to an open question raised in [MR02] regarding the security of their RSA based scheme, by showing that it is transitively unforgeable under adaptive chosen-message attack assuming the security of RSA under one-more-inversion. Finally we present a similar hash-based modification of this scheme that results in a performance improvement.
See full version | Powerpoint presentation