Practical Oblivious RAM and its Applications

Motivated by various reasons, including cost advantages, reliability and convenience, individuals and corporations are frequently outsourcing their data to public cloud platforms such as Amazon AWS, Apple iCloud, and Microsoft Skydrive. If a user wishes to ensure privacy of their data from the cloud provider, they must of course encrypt it before uploading. Unfortunately, this might not be enough. When, where and how the data is accessed from the cloud can often reveal as much or more private information than the data itself. This access pattern also needs to be hidden from the cloud provider to ensure maximum privacy.;Currently, the main cryptographic construction used to provide this hiding is called Oblivious RAM. When the user accesses data on the server, they also shuffle and reencrypt portions of the data so that two accesses to the same file can't be recognized as being the same. Although ORAM constructions have existed with good asymptotic complexity, there remain several barriers to adoption in regards to practical performance and usability. This dissertation addresses some of those problems in an effort to make ORAM practical for real world applications.;First, we study how bandwidth can be drastically reduced by taking advantage of not only the storage ability of the cloud, but its computational capabilities as well. Using recent advances in homomorphic encryption, ORAM schemes can be augmented to trade communication complexity for server computation, which is comparatively very cheap on current cloud platforms.;Beyond the traditional concern of communication complexity, there are additional usability problems that ORAM constructions have to consider. We show how constructions relying initially on a fixed size database (an unfortunately requirement for the cloud, which counts scalability as one of its main assets) can be expanded to allow dynamic resizing. We also show how to create the first ORAM construction which is secure for multiple concurrent users. Previous schemes support only a single user.;Finally, we show that for some specific use cases a restricted type of write-only ORAM can be used to achieve sufficient privacy while drastically reducing the user's overhead. We also show that this ORAM is independently interesting for hidden volume disk encryption, and provide some of the first formal definitions for such encryption schemes.