Oblivious RAM with Worst-Case Logarithmic Overhead

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.