Cryptology ePrint Archive: Report 2018/268

Oblivious RAM with Small Storage Overhead

Michael Raskin and Mark Simkin

Abstract: In this work, we present a new approach to constructing Oblivious RAM (ORAM). Somewhat surprisingly, and despite the large amount of research interest that ORAM has received, all existing ORAM constructions are based on a handful of conceptually different approaches. We believe it is of theoretical and practical interest to explore new ways to construct this primitive.

Our first construction is conceptually extremely simple and has a worst-case bandwidth overhead of $\mathcal{O}\left(\sqrt{N} \frac{\log{N}}{\log{\log{N}}}\right)$, where N is the number of data blocks.

Our main construction, Lookahead ORAM, has a worst-case bandwidth overhead of $\mathcal{O}\left(\sqrt{N}\right)$ and an additive storage overhead of $\sqrt{2N}$, which is the smallest concrete storage overhead among all existing ORAM constructions with sublinear worst-case bandwidth overhead. A small storage overhead is particularly beneficial in outsourced storage settings, where data owners have to pay their storage provider for the amount of storage they consume.

In addition to having a small storage overhead, Lookahead ORAM has perfect correctness, i.e. every operation on the ORAM data structure succeeds with probability 1 and, assuming the client stores some small stash of data locally, an online bandwidth overhead of $\mathcal{O}\left(1\right)$ without server-side computation. In comparison with prior work that has sublinear worst-case bandwidth overhead, Lookahead ORAM is asymptotically the most efficient ORAM with perfect correctness.

Category / Keywords: Oblivious RAM

Date: received 13 Mar 2018, last revised 13 Mar 2018

Contact author: simkin at cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20180313:185215 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]