Aarhus University Seal / Aarhus Universitets segl

Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead

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

  • 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 languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2019 : 25th International Conference on the Theory and Application of Cryptology and Information Security Kobe, Japan, December 8–12, 2019 Proceedings
EditorsSteven D. Galbraith, Shiho Moriai
Number of pages7
Place of publicationCham
Publication year2019
ISBN (print)978-3-030-34620-1
ISBN (Electronic)978-3-030-34621-8
Publication statusPublished - 2019
Event25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019 - Kobe, Japan
Duration: 8 Dec 201912 Dec 2019


Conference25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 176293216