Abstract
We present a novel design for stateless transitive signature ( TSTS ) for undirected graph to authenticate dynamically growing graph data. Our construction is built on the widely studied ZSSZSS signature technology [19] with bilinear mapping, and using general cryptographic hash functions (e.g., SHASHA -512 and MD6MD6 ). Compared with the existing stateless TSTS schemes for undirected graph in the literature, our scheme is more efficient. The scheme is also proven transitively unforgeable against adaptive chosen-message attack under the M2SDHM2SDH assumption in the random oracle model.