Abstract
Secure data sharing in multi-party environments such as cloud computing requires that both authenticity and confidentiality of the data be assured. Digital signature schemes are commonly employed for authentication of data. However, no such technique exists for directed graphs, even though such graphs are one of the most widely used data organization structures. Existing schemes for DAGs are authenticity-preserving but {\em not} confidentiality-preserving, and lead to leakage of sensitive information during authentication.
In this paper, we propose two schemes on how to {\em authenticate} DAGs and directed cyclic graphs {\em without leaking}, which are the first such schemes in the literature. It is based on the structure of the graph as defined by depth-first graph traversals and aggregate signatures. Graphs are structurally different from trees in that they have four types of edges: tree, forward, cross, and back-edges in a depth-first traversal. The fact that an edge is a forward, cross 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 {\em both} authenticity-preserving and non-leaking. While providing such strong security properties, our scheme is also efficient, as supported by the performance results.
Key alpha
Cloud computing, Graphs, Non-leaking, authentication
Note
This paper is an improved version of our earlier paper~\cite: ``How to Authenticate Graphs Without Leaking'', EDBT, 2010. The improvement is in the signing. distribution and verification procedures. The performance results of Figure 9 (Signing) and Figure 10 (Verification) in the original paper have been removed in this paper after
these changes.
