Paper 2018/268

Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead

Michael Raskin and Mark Simkin

Abstract

Oblivious RAM (ORAM) has established itself as a fundamental cryptographic building block. Understanding which bandwidth overheads are possible under which assumptions has been the topic of a vast amount of previous works. In this work, we focus on perfectly secure ORAM and we present the first construction with sublinear bandwidth overhead in the worst-case. All prior constructions with perfect security require linear communication overhead in the worst-case and only achieve sublinear bandwidth overheads in the amortized sense. We present a fundamentally new approach for construction ORAM and our results significantly advance our understanding of what is possible with perfect security. Our main construction, Lookahead ORAM, is perfectly secure, has a worst-case bandwidth overhead of $\mathcal{O}(\sqrt{n})$, and a total storage cost of $\mathcal{O}(n)$ on the server-side, where $n$ is the maximum number of stored data elements. In terms of concrete server-side storage costs, our construction has the smallest storage overhead among all perfectly and statistically secure ORAMs and is only a factor 3 worse than the most storage efficient computationally secure ORAM. Assuming a client-side position map, our construction is the first, among all ORAMs with worst-case sublinear overhead, that allows for a $\mathcal{O}(1)$ online bandwidth overhead without server-side computation. Along the way, we construct a conceptually extremely simple statistically secure ORAM with a worst-case bandwidth overhead of $\mathcal{O}(\sqrt{n}\frac{\log{n}}{\log{\log{n}}})$, which may be of independent interest.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
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

BibTeX

@misc{cryptoeprint:2018/268,
      author = {Michael Raskin and Mark Simkin},
      title = {Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead},
      howpublished = {Cryptology ePrint Archive, Paper 2018/268},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/268}},
      url = {https://eprint.iacr.org/2018/268}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.