Paper 2019/1108

Lower Bounds for Multi-Server Oblivious RAMs

Kasper Green Larsen, Mark Simkin, and Kevin Yeo

Abstract

In this work, we consider the construction of oblivious RAMs (ORAM) in a setting with multiple servers and the adversary may corrupt a subset of the servers. We present an $\Omega(\log n)$ overhead lower bound for any $k$-server ORAM that limits any PPT adversary to distinguishing advantage at most $1/4k$ when only one server is corrupted. In other words, if one insists on negligible distinguishing advantage, then multi-server ORAMs cannot be faster than single-server ORAMs even with polynomially many servers of which only one unknown server is corrupted. Our results apply to ORAMs that may err with probability at most $1/128$ as well as scenarios where the adversary corrupts larger subsets of servers. We also extend our lower bounds to other important data structures including oblivious stacks, queues, deques, priority queues and search trees.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in TCC 2020
Keywords
Oblivious RAMLower bound
Contact author(s)
larsen @ cs au dk
kwlyeo @ google com
simkin @ cs au dk
History
2020-11-13: revised
2019-09-29: received
See all versions
Short URL
https://ia.cr/2019/1108
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1108,
      author = {Kasper Green Larsen and Mark Simkin and Kevin Yeo},
      title = {Lower Bounds for Multi-Server Oblivious {RAMs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/1108},
      year = {2019},
      url = {https://eprint.iacr.org/2019/1108}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.