Paper 2018/471

Efficient Range ORAM with $\mathbb{O}(\log^{2}{N})$ Locality

Anrin Chakraborti and Adam J. Aviv and Seung Geol Choi and Travis Mayberry and Daniel S. Roche and Radu Sion

Abstract

Oblivious RAM protocols (ORAMs) allow a client to access data from an untrusted storage device without revealing to that device any information about their access pattern. Typically this is accomplished through shuffling the data into random positions such that the storage device is not sure where individual blocks are located, resulting in an access pattern on the device which is highly randomized. However, storage devices are usually optimized for \emph{sequential} accesses, meaning that ORAMs can often induce a substantial overhead (in addition to their increased bandwidth) due to large numbers of disk seeks (Blass et al., CCS 2014). In this paper, we present an ORAM construction specifically suited for accessing ranges of sequential logical blocks while minimizing disk seeks. Our construction obtains better asymptotic efficiency than prior work with similar security guarantees (Asharov et al., 2017), achieving $\mathbb{O}(r\cdot\log^2 N)$ communication cost (where $r$ is the size of the range) and $\mathbb{O}(\log^2 N)$ seeks per access, regardless of $r$. This is an improvement of more than a $\mathbb{O}(\log N)$ factor in both metrics when compared to prior work. In evaluation, we find that our construction is 30-50x times faster than Path ORAM for similar workloads on local HDDs, almost 30x faster for local SSDs, and 10x faster for network block devices.

Note: Fixes in Abstract