A new approach,based on one-way accumulators,to authenticate a transitively closed undirected graph was proposed.To sign a graph G,the signer accumulates each equivalence class of the vertices set of G and assigns a certification Cert,which is a partially accumulated value,to each vertices of G.To verify whether a pair (u,v) is belong to G or not,given respectively the Certs of u and v,anyone invokes a one-way accumulator to compute the accumulated values.Both two values are equal to the accumulated value of a certain equivalence class means that there is a edge between u and v in G.Thanks to one-way accumulators which replace the standard digital signatures,the signature on edges is eliminated.Compared to classical transitive signature schemes MRTS and RSATS-1,the scheme achieved smaller storage and higher efficiency.Furthermore,the scheme,allowing G to delete and add vertices and edges dynamically,provided an answer to an open question,raised by Micali and Rivest,how to authenticate a graph whose vertices and edges may be deleted dynamically.
