# Mark Simkin

## Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

### DOI

• Michael Raskin, Technical University of Munich
• ,
• Mark Simkin
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 \emph{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 constructing 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 $\bigO{\sqrt{n}}$, and a total storage cost of $\bigO{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 $\bigO{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 $\bigO{\sqrt{n}\frac{\log{n}}{\log{\log{n}}}}$, which may be of independent interest.
Original language English Advances in Cryptology – ASIACRYPT 2019 : 25th International Conference on the Theory and Application of Cryptology and Information Security Kobe, Japan, December 8–12, 2019 Proceedings Steven D. Galbraith, Shiho Moriai 7 II Cham Springer 2019 537-563 978-3-030-34620-1 978-3-030-34621-8 https://doi.org/10.1007/978-3-030-34621-8_19 Published - 2019 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019 - Kobe, JapanDuration: 8 Dec 2019 → 12 Dec 2019

### Conference

Conference 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019 Japan Kobe 08/12/2019 → 12/12/2019
Series Lecture Notes in Computer Science 11922 0302-9743

Citationformats

ID: 176293216