Authenticating Multi-Dimensional Query Results in Data Publishing

Authenticating Multi-Dimensional Query Results in Data Publishing

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-dim...

Full description

Saved in:
Bibliographic Details
Main Authors: CHENG, Weiwei, PANG, Hwee Hwa, TAN, Kian-Lee
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2006
Subjects:
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
Online Access:https://ink.library.smu.edu.sg/sis_research/285
https://ink.library.smu.edu.sg/context/sis_research/article/1284/viewcontent/Authenticating_Multi_Dimensional_Query_Results_in_Data_Publishing__edited_.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary: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.

Similar Items