Welcome to the resource topic for 2019/1108
Title:
Lower Bounds for Multi-Server Oblivious RAMs
Authors: Kasper Green Larsen, Mark Simkin, 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.
ePrint: https://eprint.iacr.org/2019/1108
Talk: https://www.youtube.com/watch?v=z6AQNahnQoE
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .