Root ORAM: A Tunable Differentially Private Oblivious RAM
Sameer Wagh, Paul Cuff, Prateek Mittal · arXiv (Cornell University) · 2016
State-of-the-art mechanisms for oblivious RAM (ORAM) suffer from significant bandwidth overheads (greater than 100x) that impact the throughput and latency of memory accesses. This renders their deployment in high-performance and bandwidth-constrained applications difficult, motivating the design of low-overhead approaches for memory access obfuscation. In this work, we introduce and formalize the notion of a differentially private ORAM that provides statistical privacy guarantees, and which to the extent of our knowledge, is the first of its kind. The formalization of differentially private ORAM opens up a large design space of low-bandwidth ORAM protocols that can be deployed in bandwidth constrained applications. We present Root ORAM, a family of practical ORAMs that provide a tunable, multi-dimensional trade-off between the desired bandwidth overhead, outsourcing ratio (ratio of the data outsourced to local storage required) and the system security, and that provide rigorous privacy guarantees of differentially private ORAMs. Root ORAM protocols can be tuned to achieve application-specific bandwidth constraints, enabling practical deployment, at the cost of statistical privacy guarantees quantified under the differential privacy framework and lower outsourcing ratios. We demonstrate the practicality of Root ORAM using theoretical analysis, simulations, as well as experiments on Amazon EC2. Our theoretical analysis rigorously quantifies the privacy offered by Root ORAM, and provably bounds the information leaked from observing memory access patterns. Our experimental analysis shows the feasibility of these protocols using realistic simulations. The simplest protocol in the Root ORAM family requires a bandwidth of mere 10 blocks, at the cost of rigorously quantified security loss and a low outsourcing ratio. This is an order of magnitude improvement over the existing state-of-the-art.