Privacy-protecting index for outsourced databases

In this paper, we present dithered B-tree, a B-tree index structure that can serve as a building block for realizing efficient system implementations in the area of secure and private database outsourcing. A dithered B-tree prevents a third party that searches this index structure from learning whether or not the search term (i.e., key) is present in the database. This privacy-related property is crucial in application domains where the party responsible for answering a query is not allowed to learn whether a specific value exists in the database.