About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Int. J. Inf. Secur.
Paper
Privacy-preserving authentication of trees and graphs
Abstract
Secure data sharing in third-party environments such as the cloud requires that both authenticity and confidentiality of the data be assured, especially when such structures encode sensitive information (such as in XML documents). Existing authentication schemes for trees and directed acyclic graphs (DAGs) are authenticity-preserving, but not confidentiality-preserving, and lead to leakage of sensitive information during authentication. In this paper, we propose a family of three leakage-free authentication schemes for (1) tree data structures, (2) directed acyclic graphs (DAGs), and (3) graphs (with cycles), which are also efficient. This family of schemes referred to as the "structural signatures" is based on the structure of the tree as defined by tree traversals and aggregate signatures. We also show through complexity and performance analysis that our scheme is practical in terms of the cost for authentication of data. We have also discussed two applications of the proposed scheme: (1) automatic correction and recovery from structural errors, and (2) secure publish /subscribe of XML documents. © 2013 Springer-Verlag Berlin Heidelberg.