Structural Signatures: How to Authenticate Trees Without Leaking

Get BibTex-formatted data

Author

Ashish Kundu, Elisa Bertino

Tech report number

CERIAS TR 2010-08

Entry type

techreport

Abstract

Data sharing over a third-party distribution framework such as the cloud computing paradigm requires that both data authenticity 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 authenticity and confidentiality be assured not only for the content, but also for the structure. There is a plethora of work on data authentication in the literature; however, none of them address the problem of leakage-free authentication of tree-structured data, especially when such structures encode sensitive information (such as in XML documents). The most widely used technique for trees is the Merkle hash technique (MHT), which however is known to be ``not hiding'', i.e., it leads to leakage of information. Most existing data authentication techniques are based on the MHT and thus suffer from the problem of information leakages. In this paper, we propose the first leakage-free authentication scheme for tree data structures, which is also efficient. Our scheme, referred to as the ``structural authentication scheme'' is based on the structure of the tree as defined by tree traversals, and aggregate signatures. In addition to formally defining the technique, we prove that it protects against violations of content and structural integrity and information leakages. Complexity analysis shows that our scheme incurs comparable cost for signing and user-side authentication, and less communication overhead while providing stronger security properties. We also have shown how our scheme can handle leakage-free authentication of dynamic trees. Two applications of the proposed scheme are presented: (1) automatic correction and recovery from structural errors, and (2) structure-based routing secure publish/subscribe of XML documents.

Date

2010 – 6 – 25

Institution

Computer Science & CERIAS

Key alpha

Cloud computing, XML, Tree data, integrity assurance, privacy, leakage-free

Note

This paper is a major extension and an improved version of our earlier paper: ``Structural Signatures for Tree Data Structures'', PVLDB, 2008. This paper (and its future publication, if any) "overrides" the VLDB paper.

School

Purdue University

Publication Date

2010-06-25

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Techreport{ Cloud computing, XML, Tree data, integrity assurance,   privacy, leakage-free,
	title = "Structural Signatures: How to Authenticate Trees Without Leaking",
	author = "Ashish Kundu, Elisa Bertino",
	year = "2010",
	month = "6",
	institution = "Computer Science & CERIAS",
	note = "This paper is a major extension and an improved version of
our earlier paper: ``Structural Signatures for Tree Data Structures'', PVLDB, 2008. This paper (and its future publication, if any) "overrides" the VLDB paper.",
	school = "Purdue University",
	day = "25",
	abstract = "Data sharing over a  third-party distribution framework such as the cloud computing paradigm  requires that both data authenticity 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 authenticity and confidentiality be assured not only for the content, but also for the structure. There is a plethora of work on data authentication in the literature; however, none of them address the problem of leakage-free authentication of tree-structured data, especially when such structures encode sensitive information (such as in XML documents). The most widely used technique for trees is the Merkle hash technique (MHT), which however is known to be ``not hiding'', i.e., it leads to leakage of information. Most existing data authentication techniques are based on the MHT and thus suffer from the problem of information leakages. In this paper, we propose the first leakage-free authentication scheme for tree data structures, which is also efficient. Our scheme, referred to as the ``structural authentication scheme'' is based on the structure of the tree as defined by tree traversals, and aggregate signatures. In addition to formally defining the technique, we prove that it protects against violations of content and structural integrity and information leakages. Complexity analysis shows that our scheme incurs comparable cost for signing and user-side  authentication, and less communication overhead while providing stronger security properties. We also have shown how our scheme can handle leakage-free authentication of dynamic trees. Two applications of the proposed scheme are presented: (1) automatic correction and recovery from structural errors, and (2) structure-based routing secure publish/subscribe of XML documents.",
}