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 \(\varOmega (\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.