When Encrypting Cloud Storage is not Enough: Concealing Access Patterns for Privacy
Encryption is not always enough to ensure privacy. If an untrusted server (or cloud provider) observes access patterns to encrypted storage, it can extract sensitive information about your private data. For example, Islam et. al. demonstrate that access patterns can leak (through statistical inference) up to 80% of the search queries made to an encrypted email repository. This type of privacy leak is especially troubling as cloud storage becomes increasingly popular. Oblivious RAM (ORAM) protocols solve this problem by continuously shuffling data as it is being accessed.
Until recently, Oblivious RAM algorithms have mostly been a theoretical problem. We introduced several techniques that make Oblivious RAM practical for the first time, including the design of a new oblivious storage system that is 63 times less bandwidth consuming. We also built a secure processor that hides arbitrary application behavior through the use of hardware-accelerated ORAM. Our techniques are very generic and powerful and allow us to build a new category of privacy-preserving applications in the cloud.