2. In a UDVTS scheme, instead of sending a transitive signature to Cindy, Alice (the owner of a transitive signature) can use
Cindy’s public key to transform a transitive signature into a UDVTS for Cindy. Upon receiving the signature, Cindy can use
the signer’s public key and her own private key to verify UDVTS. A valid UDVTS can convince only Cindy about the validity
of transitive signatures because Cindy can use her private key to create a valid UDVTS, which is indistinguishable from the
one created by Alice. Thus, the privacy of a member-relationship in an administrative domain is protected and all desir-
able properties of transitive signatures are preserved.
3. We present formal definitions and a concrete construction of UDVTS, with rigorous security proofs under the random ora-
cle model. Our UDVTS scheme can effectively address privacy issues in big data associated with dissemination of transi-
tive signatures.
1.2. Organization
The rest of the paper is organized as follow. We describe some related works in Section 2. In Section 3, we present some
preliminaries required by this paper. Section 4 presents formal definitions of UDVTS and its security models. In Section 5,we
describe our UDVTS scheme with security and performance analysis. We conclude this paper in Section 6.
2. Related works
2.1. Transitive signatures
In 2002, Micali and Rivest [23] proposed the first transitive signature scheme based on the discrete logarithm assump-
tion; In the same paper, they presented another transitive signature scheme based on RSA assumption. Their first scheme
was proven to be transitively unforgeable under adaptive chosen message attacks, while the second was merely proven tran-
sitively unforgeable under non-adaptive chosen message attacks. Later, Bellare and Neven [3,4] proposed other schemes
based on one-more RSA-inversion assumption, factoring assumption, one-more discrete logarithm assumption and one-
more gap Diffie-Hellman assumption. All these schemes were proven to be transitively unforgeable under adaptive chosen
message attacks in the standard model. Then, they eliminated node certificates for some of the above schemes by specifying
the public label of a node i as the output of a hash function applied to i. These schemes were proven to be secure in the ran-
dom oracle model. Wang et al. [29] proposed transitive signature schemes based on braid groups in the random oracle
model. Gong et al. [13] constructed a transitive signature scheme from Linear Feedback Sequence Register (LFSR).
The above transitive signature schemes are for undirected graphs only, and the problem of transitive signature schemes
for directed graphs has been open since the primitive raised by Micali and Rivest [23]. In fact, Hohenberger [14] provided
evidence that directed transitive signature schemes may be very hard to construct, because the edge signatures in such
schemes form a special mathematical group, called Abelian trapdoor group with infeasible inversion, which is not known
to exist. In 2007, Yi [30] proposed a directed transitive signature scheme for a special case that the directed graph is a
Fig. 1. Administrative domain (a graph-based big data system).
Table 1
Comparison of different approaches.
Approach Signing complexity Communication overhead
Sign the entire graph
Oðn
2
Þ
Oð1Þ
Sign the transitive reduction OðnÞ OðnÞ
Transitive signature OðnÞ Oð1Þ
146 S. Hou et al. / Information Sciences 318 (2015) 144–156