Abstract
In this paper, we address the problem of how to authenticate sub-trees (sub-graphs) without leakage of information. Previous schemes for tree (graph)-organized data, such as XML documents, authenticate information recorded in tree (graph) nodes, but leak structural information that the data receiver is not entitled to access.
This is often unacceptable, as the value of a tree (graph)-organized data is not only in the contents of the tree (graph) nodes but also in the tree (graph) structure (such as in healthcare and military data). A possible approach would be to store a pre-signed hash for each subset of the tree (graph). Such an approach is however not suitable even for moderate-size trees (graphs) because of the
exponential number of such subsets. This paper proposes authentication schemes for trees and graphs (with or without cycles). The schemes are provably secure and efficient in that the number of signatures computed for trees is \bigoh and for graphs is \bigoh, where $m$ is the number of nodes. The schemes are highly scalable - they accommodate trees and graphs with high branching factors and
extremely large numbers of nodes, such as in the order of millions. The efficiency is corroborated by our experimental results. Branching factors of 100 and 300 (which result in trees with nodes as many as 1 million and 27 millions,
respectively, with the height being 3) are handled by the proposed schemes quite efficiently. We also describe how our scheme for graphs can be used to authenticate forests without leaking.
Key alpha
Cloud computing, leakage-free signatures, trees, graphs, forests
