International Association for Cryptologic Research

International Association
for Cryptologic Research


Oblivious RAM with Worst-Case Logarithmic Overhead

Gilad Asharov , Bar-Ilan University
Ilan Komargodski , Hebrew University and NTT Research
Wei-Kai Lin , Cornell University
Elaine Shi , Carnegie Mellon University
DOI: 10.1007/978-3-030-84259-8_21 (login may be required)
Search ePrint
Search Google
Conference: CRYPTO 2021
Abstract: We present the first Oblivious RAM (ORAM) construction that for $N$ memory blocks supports accesses with \emph{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 \emph{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 \emph{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.
Video from CRYPTO 2021
  title={Oblivious RAM with Worst-Case Logarithmic Overhead},
  author={Gilad Asharov and Ilan Komargodski and Wei-Kai Lin and Elaine Shi},