  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.
