Lower Bounds for Multi-Server Oblivious RAMs
Lower Bounds for Multi-Server Oblivious RAMs
复制标题
多服务器 Oblivious RAM 的下限
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Kevin Yeo
中科院分区：
文献类型：
--
作者：
Kasper Green Larsen;Mark Simkin;Kevin Yeo
在这项工作中，我们考虑了在具有多个服务器的设置中构建无关ram (ORAM)，并且攻击者可能会破坏服务器的一个子集。我们提出了一个Ω（log n）开销下界，用于任何k服务器ORAM，限制任何PPT对手在只有一台服务器损坏时最多区分1 / 4 k的优势。换句话说，如果一个人坚持忽略不计的区别优势，那么多服务器oram不能比单服务器oram快，即使有多项式多个服务器，其中只有一个未知服务器损坏。我们的结果适用于错误概率最多为1 / 8的oram，以及攻击者破坏更大的服务器子集的场景。我们还将下界扩展到其他重要的数据结构，包括遗忘堆栈、队列、队列、优先队列和搜索树。
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 Ω(log n ) overhead lower bound for any k -server ORAM that limits any PPT adversary to distinguishing advantage at most 1 / 4 k 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 / 8 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.