Universal designated verifier transitive signatures for graph-based big data

In this paper, we propose a new type of digital signatures which is specifically designed for graph-based big data system. The properties of the proposed signatures are twofold. On one side it possesses the features of transitive signatures: One can sign a graph in such a way that, given two signatures on adjacent edges (i,j) and (j,k), anyone with public information can compute a signature on edge (i,k). The efficiency advancement (O(1) communication overhead) in transitive signatures is especially important in big data paradigm. On the other side, it is universal designated verifiable: It allows any signature holder to prove to a designated verifier that a message has been signed by the signer, but the verifier cannot convince (even sharing all secret information) any other third party of this fact. The new notion is called Universal Designated Verifier Transitive Signatures (UDVTS for short). As an integration of transitive signatures and universal designated verifier signatures, UDVTS can efficiently address privacy issues associated with dissemination of transitive signatures of graph-based big data. We further prove that our proposed design is secure in the random oracle model.