Query Authentication and processing on outsourced databases

Abstract

In Outsourced Database model, data owners publish their data management requests through a number of remote, un-trusted external service providers. Service providers host owners? databases and offer seamless mechanisms to create, store, update and access (query) their databases. This model introduces several research issues related to data security. In this thesis, we introduce a mechanism for users to verify that their query answers on a multi-dimensional dataset are correct, in the sense of being complete and authentic. Two instantiations of the approach are studied :( 1) Verifiable KD-tree (VKDtree) that is based on space partitioning, and (2)Verifiable R-tree (VR-tree) that is based on data partitioning. The schemes are evaluated on window queries, and results show that VR-tree is highly precise, meaning that few data points outside of a query result are disclosed in the course of proving its correctness. Moreover, as an extension of the VR-tree, we proposed a mechanism that extend the signature-based mechanism for users to verify that their answers for k nearest neighbors queries on a multidimensional dataset are complete (i.e. no qualifying data points are omitted), authentic (i.e. no answer points are tampered) and minimal (i.e., no non-answer points are returned in the plain). Essentially, our scheme returns k answer points in the plain, and a set of (~p; q)-pairs of points, where ~p is the digest of a non-answer point p in the dataset to facilitate the signature chaining mechanism to verify the authenticity of the answer points, and q is a reference point (not in the dataset) used to verify that p is indeed further away from the kth nearest point. We study two instantiations of the approach ? one based on the native data space using space partitioning method (a.k.a. R-tree) and the other based on the metric space using iDistance. We conducted an experimental study, and report our findings here.