Path Oblivious Heap: Optimal and Practical Oblivious Priority Queue
Path Oblivious Heap: Optimal and Practical Oblivious Priority Queue
复制标题
路径遗忘堆：最优实用的遗忘优先级队列
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
E. Shi
中科院分区：
文献类型：
--
作者：
E. Shi
我们提出了路径不经意堆，这是一种非常简单、实用和最优的不经意优先级队列。我们的构造还蕴含了一种实用的最优不经意排序算法，我们称之为路径不经意排序。我们的算法不仅是渐近最优的，我们还证明了它们的实际性能只比不安全的基线差一个小的恒定因素。更具体地说，假设客户端私有存储空间大致为对数，路径不经意堆消耗的带宽比普通的不安全二进制堆多2×到7倍；路径不经意排序比不安全合并排序消耗的带宽多4.5×到6倍。我们表明，这些性能结果使现有的工作提高了1-2个数量级。最后，我们针对多方计算场景对我们的算法进行了评估，结果表明，与ART1的状态相比，对称加密的数量减少了7倍到8倍。
We propose Path Oblivious Heap, an extremely simple, practical, and optimal oblivious priority queue. Our construction also implies a practical and optimal oblivious sorting algorithm which we call Path Oblivious Sort. Not only are our algorithms asymptotically optimal, we show that their practical performance is only a small constant factor worse than insecure baselines. More specificially, assuming roughly logarithmic client private storage, Path Oblivious Heap consumes 2× to 7× more bandwidth than the ordinary insecure binary heap; and Path Oblivious Sort consumes 4.5× to 6× more bandwidth than the insecure Merge Sort. We show that these performance results improve existing works by 1-2 orders of magnitude. Finally, we evaluate our algorithm for a multi-party computation scenario and show 7x to 8x reduction in the number of symmetric encryptions relative to the state of the art1.