Providing Query Assurance for Outsourced Tree-Indexed Data

Outsourcing database services is emerging as an important new trend thanks to continued developments of the Internet and advances in the networking technology. In this outsourced database service model, organizations rely upon the premises of an external service provider for the storage and retrieval management of their data. Since a service provider is typically not fully trusted, this model introduces numerous interesting research challenges. Among them, most crucial security research questions relate to (1) data confidentiality, (2) user privacy, (3) data privacy, and (4) query assurance. Although there exist a number of research work on these topics, to the best of our knowledge, none of them has dealt with ensuring query assurance for outsourced tree-indexed data. To address this issue, the system must prove authenticity and data integrity, completeness and, not less importantly, provide freshness guarantees for the result set. These objectives imply that (1) data in the result set is originated from the actual data owner and has not been tampered with; (2) the server did not omit any tuples matching the query conditions; and (3) the result set was generated with respect to the most recent snapshot of the database. This is not a trivial task, especially as tree-based index structures are outsourced to untrusted servers. In this paper, we discuss and propose solutions to security issues in order to provide query assurance for outsourced databases that come together with tree-based index structures. Our techniques allow users to operate on their outsourced tree-indexed data on untrusted servers with high query assurance and at reasonable costs. Experimental results with real datasets confirm the efficiency of our approach and theoretical analysis.