Ilan Komargodski: A Logarithmic Lower Bound for Oblivious RAM (for all parameters)

An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e., for every input the observed locations accessed are similarly distributed. In recent years there has been great progress both in terms of upper bounds as well as in terms of lower bounds, essentially  pinning down the smallest overhead possible in various settings of parameters.

 

In this talk I will describe a recent work related to proving lower bounds for ORAM. Specifically, we will show that any ORAM must make logarithmically many physical accesses per each logical query, amortized. The lower bound will hold for any reasonable choice of word sizes and block sizes. An application of this result is an unconditional separation between online and offline ORAM.