Differentially Private Oblivious RAM
This work addresses the need for efficient and private data access in secure systems like trusted execution environments and cloud storage, offering tunable trade-offs, though it is incremental as it builds on existing ORAM methods with statistical privacy enhancements.
The paper tackles the problem of enhancing Oblivious RAM (ORAM) performance with statistical privacy by proposing a differentially private ORAM framework called Root ORAM, which reduces local storage overhead by about 2x and bandwidth overheads by up to 2x-10x for memory-limited and cloud environments.
In this work, we investigate if statistical privacy can enhance the performance of ORAM mechanisms while providing rigorous privacy guarantees. We propose a formal and rigorous framework for developing ORAM protocols with statistical security viz., a differentially private ORAM (DP-ORAM). We present Root ORAM, a family of DP-ORAMs that provide a tunable, multi-dimensional trade-off between the desired bandwidth overhead, local storage and system security. We theoretically analyze Root ORAM to quantify both its security and performance. We experimentally demonstrate the benefits of Root ORAM and find that (1) Root ORAM can reduce local storage overhead by about 2x for a reasonable values of privacy budget, significantly enhancing performance in memory limited platforms such as trusted execution environments, and (2) Root ORAM allows tunable trade-offs between bandwidth, storage, and privacy, reducing bandwidth overheads by up to 2x-10x (at the cost of increased storage/statistical privacy), enabling significant reductions in ORAM access latencies for cloud environments. We also analyze the privacy guarantees of DP-ORAMs through the lens of information theoretic metrics of Shannon entropy and Min-entropy [16]. Finally, Root ORAM is ideally suited for applications which have a similar access pattern, and we showcase its utility via the application of Private Information Retrieval.