View article

Abstract An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM 1996), is a (probabilistic) RAM that hides its access pattern, ie, 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. We observe that there is a very natural setting of parameters in which no non-trivial lower bound is known, even not ones in restricted models of computation (like the so called balls and bins model). Let N and w w be the number of cells and bit-size of cells, respectively, in the RAM that we wish to simulate obliviously. Denote by b b the cell bit-size of the ORAM. All previous ORAM lower bounds have a multiplicative w/b w/b factor which makes them trivial in many settings of parameters of interest …