【摘要】 提出了使用单向累加器进行无向可传递闭包图认证的新方法,构造了具体认证方案。签名时,签名者对节点集合的等价类进行累加,并为节点签发包含部分累加值的证书。累加值构成了图的签名,证书表明了节点对等价类的所属关系。验证时,只需对相关节点的证书做一次累加运算,便可验证节点间边的存在性。通过与典型的可传递签名方案的比较,表明新方案所需的空间复杂度和时间复杂度更小。另外,新方案同时支持节点和边的动态增删,这解决了Micali和Rivest提出的一个公开问题。更多还原

【Abstract】 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 certifi- cation 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.更多还原