Paper 2021/1123

Oblivious RAM with Worst-Case Logarithmic Overhead

Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, and Elaine Shi

Abstract

We present the first Oblivious RAM (ORAM) construction that for $N$ memory blocks supports accesses with worst-case $O(\log N)$ overhead for any block size $\Omega(\log N)$ while requiring a client memory of only a constant number of memory blocks. We rely on the existence of one-way functions and guarantee computational security. Our result closes a long line of research on fundamental feasibility results for ORAM constructions as logarithmic overhead is necessary. The previous best logarithmic overhead construction only guarantees it in an amortized sense, i.e., logarithmic overhead is achieved only for long enough access sequences, where some of the individual accesses incur $\Theta(N)$ overhead. The previously best ORAM in terms of worst-case overhead achieves $O(\log ^2 N/\log\log N)$ overhead. Technically, we design a novel de-amortization framework for modern ORAM constructions that use the ``shuffled inputs'' assumption. Our framework significantly departs from all previous de-amortization frameworks, originating from Ostrovsky and Shoup (STOC '97), that seem to be fundamentally too weak to be applied on modern ORAM constructions.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2021
DOI
10.1007/978-3-030-84259-8_21
Keywords
Oblivious RAM
Contact author(s)
Gilad asharov @ biu ac il
weikaili @ cs cmu edu
runting @ gmail com
ilankom10 @ gmail com
History
2022-03-08: revised
2021-09-06: received
See all versions
Short URL
https://ia.cr/2021/1123
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1123,
      author = {Gilad Asharov and Ilan Komargodski and Wei-Kai Lin and Elaine Shi},
      title = {Oblivious RAM with Worst-Case Logarithmic Overhead},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1123},
      year = {2021},
      doi = {10.1007/978-3-030-84259-8_21},
      note = {\url{https://eprint.iacr.org/2021/1123}},
      url = {https://eprint.iacr.org/2021/1123}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.