Two-server Distributed ORAM with Sublinear Computation and Constant Rounds
Two-server Distributed ORAM with Sublinear Computation and Constant Rounds
复制标题
DOI：
10.1007/978-3-030-75248-4_18
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ariel Hamlin;Mayank Varia
中科院分区：
文献类型：
--
作者：
Ariel Hamlin;Mayank Varia
分布式ORAM(DORAM)是不经意RAM的多服务器变体。DORAM最初是为了降低带宽而提出的，最近由于其适用于RAM模型中的安全计算而引起了极大的兴趣，在RAM模型中，电路复杂性和通信轮数是同样重要的效率指标。所有先前的Doram构造要么涉及每个服务器的线性工作(例如，Floram)，要么涉及服务器之间的对数轮通信(例如，平方根Oram)。在这项工作中，我们在两个服务器、半诚实的环境下构造了第一个Doram方案，它同时实现了次线性服务器计算和恒定轮次通信。我们提供了两种常数轮结构，一种基于具有本地计算的平方根ORAM，另一种基于双效率PIR的安全计算，该PIR实现了对任何对象的本地计算，但允许服务器区分读和写。作为后一种构造的基础，我们提供了基于快速傅立叶变换的多元多项式求值和内插的安全计算协议，这可能是独立感兴趣的。
Distributed ORAM (DORAM) is a multi-server variant of Oblivious RAM. Originally proposed to lower bandwidth, DORAM has recently been of great interest due to its applicability to secure computation in the RAM model, where circuit complexity and rounds of communication are equally important metrics of efficiency. All prior DORAM constructions either involve linear work per server (e.g., Floram) or logarithmic rounds of communication between servers (e.g., square root ORAM). In this work, we construct the first DORAM schemes in the 2-server, semi-honest setting that simultaneously achieve sublinear server computation and constant rounds of communication. We provide two constant-round constructions, one based on square root ORAM that haslocal computation and another based on secure computation of a doubly efficient PIR that achieves local computation offor anybut that allows the servers to distinguish between reads and writes. As a building block in the latter construction, we provide secure computation protocols for evaluation and interpolation of multivariate polynomials based on the Fast Fourier Transform, which may be of independent interest.