CryptoDB
Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead
| Authors: | |
|---|---|
| Download: | |
| 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 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 , and a total storage cost of 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 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 , which may be of independent interest. |
BibTeX
@article{asiacrypt-2019-30050,
title={Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead},
booktitle={Advances in Cryptology – ASIACRYPT 2019},
series={Advances in Cryptology – ASIACRYPT 2019},
publisher={Springer},
volume={11922},
pages={537-563},
doi={10.1007/978-3-030-34621-8_19},
author={Michael Raskin and Mark Simkin},
year=2019
}