Integrity of graphs without leaking
Ashish Kundu, Elisa Bertino · Annual Information Security Symposium · 2009
Secure data sharing in multi-party data sharing environments over third-party distribution frameworks requires that both integrity and confidentiality of the data be assured. Digital signature schemes are commonly used for integrity verification of data. However no such technique exists for graphs, even though graphs are one of the most widely used data organization structures. Techniques exist for directed acyclic graphs and trees, which are restricted forms of graphs. Such techniques are integrity-preserving (binding) but not confidentiality-preserving (hiding), which lead to leakage of sensitive information during integrity verification. The recently proposed structural signature scheme for trees is both binding and hiding, however is not suitable for graphs.In this paper, we propose a signature scheme for graph structures, which is provably binding and hiding. The proposed scheme is based on the structure of the graph as defined by depth-first graph traversals. Graphs are structurally different from trees in that they have four types of edges: tree, forward, cross, and back-edges. The fact that an edge is a forward-edge, a cross-edge or a back-edge conveys information that is sensitive in several contexts. Moreover, back-edges pose a more difficult problem than the one posed by forward, and cross-edges primarily because back-edges add bidirectional properties to graphs. We prove that the proposed technique is both binding and hiding. While providing such strong security guarantees, our signature scheme is also efficient: for DAGs, it incurs $O(n)$ (linear) cost for computation, storage and distribution of structural signatures, and for cyclic graphs, it incurs $O(n+d)$ cost, where $n$ is the number of nodes and $d$ is the maximum number of back-edges incident on a node in the graph.