Paper 2020/1132
A Logarithmic Lower Bound for Oblivious RAM (for all parameters)
Ilan Komargodski and WeiKai Lin
Abstract
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. We observe that there is a very natural setting of parameters in which no nontrivial lower bound is known, even not ones in restricted models of computation (like the so called balls and bins model). Let $N$ and ${\boldsymbol w}$ be the number of cells and bitsize of cells, respectively, in the RAM that we wish to simulate obliviously. Denote by ${\boldsymbol b}$ the cell bitsize of the ORAM. All previous ORAM lower bounds have a multiplicative ${\boldsymbol w}/{\boldsymbol b}$ factor which makes them trivial in many settings of parameters of interest. In this work, we prove a new ORAM lower bound that captures this setting (and in all other settings it is at least as good as previous ones, quantitatively). We show that any ORAM must make (amortized) $$ \Omega\left(\log \left(\frac{N{\boldsymbol w}}{m}\right)/\log\left(\frac{{\boldsymbol b}}{{\boldsymbol w}}\right)\right) $$ memory probes for every logical operation. Here, $m$ denotes the bitsize of the local storage of the ORAM. Our lower bound implies that logarithmic overhead in accesses is necessary, even if $ {\boldsymbol b} \gg {\boldsymbol w}$. Our lower bound is tight for all settings of parameters, up to the $\log({\boldsymbol b}/{\boldsymbol w})$ factor. Our bound also extends to the noncolluding multiserver setting. As an application, we derive the first (unconditional) separation between the overhead needed for ORAMs in the online vs. offline models. Specifically, we show that when ${\boldsymbol w}=\log N$ and ${\boldsymbol b},m \in \mathsf{poly}\log N$, there exists an offline ORAM that makes (on average) $o(1)$ memory probes per logical operation while every online one must make $\Omega(\log N/\log\log N)$ memory probes per logical operation. No such previous separation was known for any setting of parameters, not even in the balls and bins model.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in CRYPTO 2021
 Keywords
 oblivious RAMlower boundcell probe modelcompression argument
 Contact author(s)

ilank @ cs huji ac il
wklin @ cs cornell edu  History
 20210621: revised
 20200921: received
 See all versions
 Short URL
 https://ia.cr/2020/1132
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1132, author = {Ilan Komargodski and WeiKai Lin}, title = {A Logarithmic Lower Bound for Oblivious RAM (for all parameters)}, howpublished = {Cryptology ePrint Archive, Paper 2020/1132}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1132}}, url = {https://eprint.iacr.org/2020/1132} }