Conference Proceeding Article
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.
Security of data, Trees (mathematics), Chains, Data handling, Decision trees, Query processing, Verifiable R-tree (VRtree), Authentication information, Space partitioning, data security
Databases and Information Systems | Information Security | Numerical Analysis and Scientific Computing
Data Management and Analytics; Information Security and Trust
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
City or Country
CHENG, Weiwei; PANG, Hwee Hwa; and TAN, Kian-Lee.
Authenticating Multi-Dimensional Query Results in Data Publishing. (2006). 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. 4127, 60-73. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/285
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.