University of Calgary
Outsourced data management is a large and growing industry. For example, as of July 2011, Amazon S3 reportedly stores more than 400 billion objects, which is four times its size from the year before, and the Windows Azure service, which was started in late 2008, is now a multi-billion dollar enterprise. The authors study Oblivious Storage (OS), a natural way to model privacy-preserving data outsourcing where a client, Alice, stores sensitive data at an honest-but-curious server, Bob. They show that Alice can hide both the content of her data and the pattern in which she accesses her data, with high probability, using a method that achieves O(1) amortized rounds of communication between her and Bob for each data access.