Oblivious Search and Updates for Outsourced Tree-Structured Data on Untrusted Servers
Tran Khanh Dang · International journal of computer science and applications · 2005
Although tree-based index structures, such as B+ -trees, R-trees, have proven their advantages to both traditional and modern database applications, they introduce numerous research challenges as database services are outsourced to untrusted servers. In the outsourced database service (ODBS) model, the crucial security research questions mainly relate to data confidentiality, data and user privacy, authentication and data integrity. To the best of our knowledge, however, none of the previous research has radically addressed the problem of pr eserving privacy for basic operations on such outsourced search trees. Basic operations of search trees/tree-based index structures include search (to answer different types of queries) and updates (modification, insert, delete). In this paper, we will discuss security issues in outsourced databases that come together with search trees, and present techniques to ensure privacy in the execution of these trees’ basic operations on the untrusted server. Our techniques allow clients to operate on their outsourced tree-structured data on untrusted servers without revealing information about the query, result, and the outsourced data itself.