Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

7-2006

Abstract

In data publishing, the owner delegates the role of satisfying user queries to a third-party publisher. As the publisher may be untrusted or susceptible to attacks, it could produce incorrect query results. This paper introduces a mechanism for users to verify that their query answers on a multi-dimensional dataset are correct, in the sense of being complete (i.e., no qualifying data points are omitted) and authentic (i.e., all the result values originated from the owner). Our approach is to add authentication information into a spatial data structure, by constructing certified chains on the points within each partition, as well as on all the partitions in the data space. Given a query, we generate proof that every data point within those intervals of the certified chains that overlap the query window either is returned as a result value, or fails to meet some query condition. We study two instantiations of the approach: Verifiable KD-tree (VKDtree) that is based on space partitioning, and Verifiable R-tree (VRtree) that is based on data partitioning. The schemes are evaluated on window queries, and results show that VRtree is highly precise, meaning that few data points outside of a query result are disclosed in the course of proving its correctness.

Keywords

Security of data, Trees (mathematics), Chains, Data handling, Decision trees, Query processing, Verifiable R-tree (VRtree), Authentication information, Space partitioning, data security

Discipline

Databases and Information Systems | Information Security | Numerical Analysis and Scientific Computing

Publication

Data and Applications Security XX: 20th Annual IFIP WG 11.3 Working Conference on Data and Applications Security, Sophia Antipolis, France, July 31-August 2, 2006. Proceedings

Volume

4127

First Page

60

Last Page

73

ISBN

9783540367963

Identifier

10.1007/11805588_5

Publisher

Springer Verlag

City or Country

Berlin

Additional URL

https://doi.org/10.1007/11805588_5

Download

Share

COinS