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 the 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 leakage of information. Most existing techniques for
the integrity of hierarchical data structures are based on the Merkle
hash technique and thus suffer from the problem of information leakages.
We describe the types of
leakages and inference attacks that can be carried out on the Merkle hash
technique, in the context of integrity
assurance. 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 an integrity assurance scheme for tree data
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 integrity assurance 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.
Techniques for computing randomized traversal numbers are also
described in the paper. 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 integrity assurance scheme is efficient; with respect to the Merkle hash
technique, it incurs comparable cost for signing trees and incurs lower cost
for user-side integrity verification. Further, we extend the proposed technique
in order to assure integrity of weighted trees and dynamic updates.
% As an
% example, the paper also describes a revised scheme for structure-based routing
% for secure dissemination of XML documents.
We also show how the proposed structural
integrity assurance technique can be applied in order to precisely detect
integrity violations as well as to efficiently recover data. Such
techniques have applications in digital forensics and
efficient data transmission.
Key alpha
Integrity, confidentiality, Leakage, Merkle hash, Trees, XML, Traversal
