Data-Oblivious Algorithms for Privacy-Preserving Access to Cloud Storage
Olga Ohrimenko · 2014
of “ Data-Oblivious Algorithms for Privacy-Preserving Access to Cloud Storage ” by Olga Ohrimenko, Ph.D., Brown University, May 2014 Cloud storage has emerged as the next generation of data storage where users can remotely store their data and leave its management to a third party, e.g., Amazon S3, Google Drive or Microsoft Azure. However, the fact that users no longer have physical possession of their data raises new challenges in terms of data privacy. Storing the data in encrypted form is a key component in maintaining privacy against the storage provider. However, encryption alone is not enough since information may be leaked through the pattern in which users access the data. In this thesis, we describe algorithms that allow data-oblivious access to remotely stored data. That is, access patterns of such algorithms depend only on the size of the outsourced data and algorithm input, but not their content. Hence, such algorithms reveal nothing about the data they are processing. We start by describing a general method that obliviously simulates user requests to outsourced data of size n and adds O(log n) overhead in the average case, succeeding with very high probability. This method assumes a private workspace of size O(n ) on the user side, for any given fixed positive constant , and does not maintain a state between data requests. We then show how to deamortize our method to achieve O(log n) overhead in the worst case. Our deamortization technique is general and can be applied to several existing oblivious simulations. The next oblivious simulation technique presented in this thesis improves over the O(log n) solution and demonstrates an interplay between system parameters such as latency, bandwidth, and the size of the user’s private memory. We show that if a user exchanges messages of size O(n log n) with the storage provider, for some constant c ≥ 2, and has access to private memory of the same size, then our method can achieve O(1) access overhead in the worst case with very high probability. Finally, we study application-specific access patterns and look at how to make them oblivious without using the general oblivious simulation methods mentioned above. In particular, we show how one can access and perform a computation in an oblivious fashion on an externally stored graph. We also show that a number of classic graph drawing algorithms can be efficiently implemented in this framework while maintaining user privacy.