Shuffle Index: efficient and private access to outsourced data

Data outsourcing and cloud computing have been emerging at an ever-growing rate as successful approaches for allowing users and companies to rely on external services for storing and managing data. As data and access to them are not under the control of the data owner, there is a clear need to provide proper confidentiality protection. Such requirements concern the confidentiality not only of the stored data (content) but also of the specific accesses (or patterns of them) that users make on such data. In this article, we address these issues and propose an approach for guaranteeing content, access, and pattern confidentiality in a data outsourcing scenario. The proposed solution is based on the definition of a shuffle index structure, which adapts traditional B+-trees and, by applying a combination of techniques (covers, caches, and shuffling), ensures confidentiality of the data and of queries over them, protecting each single access as well as sequences thereof. The proposed solution also supports update operations over the data, while making reads and writes not recognizable as such by the server. We show that the shuffle index exhibits a limited performance cost, thus resulting effectively usable in practice.