Efficient, Oblivious Data Structures for MPC
Efficient, Oblivious Data Structures for MPC
复制标题
DOI：
10.1007/978-3-662-45608-8_27
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
Marcel Keller;Peter Scholl
中科院分区：
文献类型：
--
作者：
Marcel Keller;Peter Scholl
我们提出了几个数据结构的安全多方计算（MPC），如数组，字典和优先级队列的遗忘实现。由此产生的不经意的数据结构只有多对数开销相比，他们的经典同行。为了实现这一点，我们给出了安全的多方协议的ORAM的石等。（Asiacrypt '11）和路径ORAM方案的Stefanov等。（CCS '13），我们比较得到的实现。随后，我们使用我们的不经意的优先级队列的安全计算的Dijkstra的最短路径算法的一般图形，其中的图形结构是秘密的。据我们所知，这是第一次实现一个非平凡的图算法在多方计算与多对数开销。我们实现和基准测试我们的大多数协议使用SPDZ协议Damgård等人。（Crypto '12），它工作在预处理模型，并确保积极的安全性，防止对手破坏所有，但一个球员。对于两方，大小为100万的遗忘数组的在线访问时间小于100 ms。
We present oblivious implementations of several data structures for secure multiparty computation (MPC) such as arrays, dictionaries, and priority queues. The resulting oblivious data structures have only polylogarithmic overhead compared with their classical counterparts. To achieve this, we give secure multiparty protocols for the ORAM of Shi et al. (Asiacrypt ‘11) and the Path ORAM scheme of Stefanov et al. (CCS ‘13), and we compare the resulting implementations. We subsequently use our oblivious priority queue for secure computation of Dijkstra’s shortest path algorithm on general graphs, where the graph structure is secret. To the best of our knowledge, this is the first implementation of a non-trivial graph algorithm in multiparty computation with polylogarithmic overhead.We implemented and benchmarked most of our protocols using the SPDZ protocol of Damgård et al. (Crypto ‘12), which works in the preprocessing model and ensures active security against an adversary corrupting all but one players. For two parties, the online access time for an oblivious array of size one million is under 100 ms.