## CryptoDB

### Paper: Oblivious RAM with Worst-Case Logarithmic Overhead

Authors: 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 CRYPTO 2021 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.
##### BibTeX
@inproceedings{crypto-2021-31171,
title={Oblivious RAM with Worst-Case Logarithmic Overhead},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-84259-8_21},
author={Gilad Asharov and Ilan Komargodski and Wei-Kai Lin and Elaine Shi},
year=2021
}