Paper 2018/373

PanORAMa: Oblivious RAM with Logarithmic Overhead

Sarvar Patel, Giuseppe Persiano, Mariana Raykova, and Kevin Yeo

Abstract

We present PanORAMa, the first Oblivious RAM construction that achieves communication overhead $O(\log N \cdot \log \log N)$ for a database of $N$ blocks and for any block size $B=\Omega(\log N)$ while requiring client memory of only a constant number of memory blocks. Our scheme can be instantiated in the ``balls and bins" model in which Goldreich and Ostrovsky [JACM 96] showed an $\Omega(\log N)$ lower bound for ORAM communication. Our construction follows the hierarchical approach to ORAM design and relies on two main building blocks of independent interest: a \emph{new oblivious hash table construction} with improved amortized $O\left( \log N + \text{poly}(\log \log \lambda) \right)$ communication overhead for security parameter $\lambda$ and $N = \text{poly}(\lambda)$, assuming its input is randomly shuffled; and a complementary \emph{new oblivious random multi-array shuffle construction}, which shuffles $N$ blocks of data with communication $O(N \log\log \lambda + \frac{N\log N}{\log \lambda})$ when the input has a certain level of entropy. We combine these two primitives to improve the shuffle time in our hierarchical ORAM construction by avoiding heavy oblivious shuffles and leveraging entropy remaining in the merged levels from previous shuffles. As a result, the amortized shuffle cost is asymptotically the same as the lookup complexity in our construction.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. MINOR revision.IEEE-FOCS-2018
Keywords
Oblivious RAMOblivious ShuffleOblivious Hash Table
Contact author(s)
kwlyeo @ google com
History
2019-08-05: last of 3 revisions
2018-04-30: received
See all versions
Short URL
https://ia.cr/2018/373
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/373,
      author = {Sarvar Patel and Giuseppe Persiano and Mariana Raykova and Kevin Yeo},
      title = {PanORAMa: Oblivious RAM with Logarithmic Overhead},
      howpublished = {Cryptology ePrint Archive, Paper 2018/373},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/373}},
      url = {https://eprint.iacr.org/2018/373}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.