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 1 and the system security, and that provide rigorous privacy guarantees of differentially private ORAMs. The 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 ORAM schemes which incur logarithmic bandwidth overheads. 1 Outsourcing ratio is defined as the amount of data that can be outsourced for a certain amount of local storage. Refer to Sec. 7 for more details.
Wagh et al. REF formalized the notion of differentially private oblivious RAM (DP ORAM) and their corresponding protocols significantly improved the bandwidth overheads with a relaxed privacy guarantee.
Root ORAM: A Tunable Differentially Private Oblivious RAM
ArXiv
ArXiv
Computer Science