You are looking at a specific version 20180313:185215 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Oblivious RAM
Contact author(s)
simkin @ cs au dk
History
2019-02-06: last of 2 revisions
2018-03-13: received
See all versions
Short URL
https://ia.cr/2018/268
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.