CryptoDB
Oblivious RAM with Worst-Case Logarithmic Overhead
| Authors: |
|
|---|---|
| Download: |
|
| 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
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
}