Structural signatures for tree data structures
Authors:
Open Access
- 1 August 2008
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 1 (1) , 138-150
Abstract
Data sharing with multiple parties over a third-party distribution framework requires that both data integrity and confidentiality be assured. One of the most widely used data organization structures is the tree structure. When such structures encode sensitive information (such as in XML documents), it is crucial that integrity and confidentiality be assured not only for the content, but also for the structure. Digital signature schemes are commonly used to authenticate the integrity of the data. The most widely used such technique for tree structures is the Merkle hash technique, which however is known to be "not hiding", thus leading to unauthorized leakage of information. Most techniques in the literature are based on the Merkle hash technique and thus suffer from the problem of unauthorized information leakages. Assurance of integrity and confidentiality (no leakages) of tree-structured data is an important problem in the context of secure data publishing and content distribution systems. In this paper, we propose a signature scheme for tree structures, which assures both confidentiality and integrity and is also efficient, especially in third-party distribution environments. Our integrity assurance technique, which we refer to as the "Structural signature scheme", is based on the structure of the tree as defined by tree traversals (pre-order, post-order, in-order) and is defined using a randomized notion of such traversal numbers. In addition to formally defining the technique, we prove that it protects against violations of content and structural integrity and information leakages. We also show through complexity and performance analysis that the structural signature scheme is efficient; with respect to the Merkle hash technique, it incurs comparable cost for signing the trees and incurs lower cost for user-side integrity verification.Keywords
This publication has 14 references indexed in Scilit:
- Detecting Information Leakage in Updating XML Documents of Fine-Grained Access ControlLecture Notes in Computer Science, 2006
- Preventing attribute information leakage in automated trust negotiation2005
- Correcting errors without leaking partial information2005
- Selective and authentic third-party distribution of XML documentsIEEE Transactions on Knowledge and Data Engineering, 2004
- A General Model for Authenticated Data StructuresAlgorithmica, 2004
- Derived access control specification for XML2003
- Tree Signatures for XML Querying and NavigationLecture Notes in Computer Science, 2003
- Flexible authentication of XML documents2001
- The BiBa one-time signature and broadcast authentication protocol2001
- An optimal algorithm for reconstructing a binary treeInformation Processing Letters, 1992