Directed Transitive Signature Scheme

In 2002, Micali and Rivest raised an open problem as to whether directed transitive signatures exist or not. In 2003, Hohenberger formalized the necessary mathematical criteria for generic directed transitive signature scheme, showing that the edge signatures in such a scheme form a special (and powerful) mathematical group, called Abelian trapdoor group with infeasible inversion, which is not known to exist. In this paper, we consider a directed graph whose transitive reduction is a directed tree, on which we propose a natural RSA-based directed transitive signature scheme

$\mathcal{RSADTS}$

. In this particular case, we have answered the open problem raised by Micali and Rivest. We have proved that

$\mathcal{RSADTS}$

, associated to a standard digital signature scheme, is transitively unforgeable under adaptive chosen-message attack if the RSA inversion problem over a cyclic group is hard and the standard digital signature is secure. Furthermore,

$\mathcal{RSADTS}$

has even better performance than

$\mathcal{RSATS}$

-1 in certain circumstance.