A practical solution to supporting oblivious basic operations on dynamic outsourced search trees
Tran Khanh Dang · 2006
Outsourcing database services is a recent trend thanks to advances in the networking technologies and continued growth of the Internet. In the outsourced database service (ODBS) model, clients rely on the premises of the provider, which include hardware, software and manpower, for the storage, maintenance, and retrieval of their data. This ODBS model brings in a variety of conveniences as well as introduces numerous research challenges, and thus has rapidly become one of the hot topics in the research community [1–6]. Because a client stores its private data at an external service provider, who is typically not fully trusted, making outsourced data confidential is one of the foremost challenges in this model. Basically, despite the untrusted server at the provider’s side, the final goal that clients want is to use the outsourced database service as an in-house one. This includes a requirement that clients can operate on their outsourced data without worrying about leak of their sensitive information. This in turn poses several additional challenges related to privacy-preserving for client’s queries as well as the outsourced data during the execution of operations at the untrusted server. Overall, with an assumption that clients are trusted (cf. section 7), the following security requirements must be met: