A novel method to authenticate transitively closed undirected graph

The transitive signature is currently the only method to sign vertices and edges of a dynamically growing, transitively closed graph. The shortcomings of transitive signatures are the large length of edge signature and the low efficiency of signing the edge. A new approach, based on one-way accumulators, to authenticate a transitively closed undirected graph is proposed. Thanks to one-way accumulator which replace the standard digital signatures, the need of a signature on its edges is eliminated, so our method achieves smaller storage and higher efficiency than transitive signatures. Furthermore, our scheme, allowing G to delete and add vertices and edges dynamically, provides an answer to an open question, raised by Micali and Rivest [1] regarding how to authenticate a graph whose vertices and edges may be deleted dynamically.