Paper 2009/209

On Directed Transitive Signature

Jia Xu, Ee-Chien Chang, and Jianying Zhou

Abstract

In early 2000's, Rivest~\cite{CambridgeTalk-Rivest,TSS-Micali} and Micali~\cite{TSS-Micali} introduced the notion of \emph{transitive signature}, which allows a third party to generate a valid signature for a composed edge $(v_i, v_k)$, from the signatures for two edges $(v_i, v_j)$ and $(v_j, v_k)$, and using the public key only. Since then, a number of works, including \cite{TSS-Micali,transig-fac-rsa-Bellare,hohenberger-masters,TSS-BilinearGroup-Shahandashti,transig-Bellare}, have been devoted on transitive signatures. Most of them address the undirected transitive signature problem, and the directed transitive signature is still an open problem. S.~Hohenberger~\cite{hohenberger-masters} even showed that a directed transitive signature implies a complex mathmatical group, whose existence is still unkown. Recently, a few directed transitive signature schemes~\cite{DirectedTSS-Yi,dtts-Neven} on directed trees are proposed. The drawbacks of these schemes include: the size of composed signature increases linearly with the number of recursive applications of composition and the creating history of composed edge is not hidden properly. This paper presents {\DTTS}---a \emph{Directed}-Tree-Transitive Signature scheme, to address these issues. Like previous works~\cite{DirectedTSS-Yi,dtts-Neven}, {\DTTS} is designed only for directed trees, however, it features with constant (composed) signature size and privacy preserving property. %oblivious composition history G.~Neven~\cite{dtts-Neven} pointed out constant signature size is an essential requirement of the original directed transitive signature problem raised by Rivest and Micali. In this sense, our scheme {\DTTS} is the \emph{first} transitive signature scheme on a directed tree. We also prove that {\DTTS} is transitively unforgeable under adaptive chosen message attack in the standard model.