Cryptology ePrint Archive: Report 2021/1123

Oblivious RAM with Worst-Case Logarithmic Overhead

Gilad Asharov and Ilan Komargodski and 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.

Category / Keywords: cryptographic protocols / Oblivious RAM

Original Publication (with major differences): IACR-CRYPTO-2021

Date: received 3 Sep 2021

Contact author: Gilad asharov at biu ac il

Available format(s): PDF | BibTeX Citation

Version: 20210906:074325 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]