Welcome to the resource topic for 2020/1547
Title:
Two-server Distributed ORAM with Sublinear Computation and Constant Rounds
Authors: Ariel Hamlin, Mayank Varia
Abstract: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. 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 has O(\sqrt{N}\log N) local computation and another based on secure computation of a doubly efficient PIR that achieves local computation of O(N^\epsilon) for any \epsilon > 0 but 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.
ePrint: https://eprint.iacr.org/2020/1547
Talk: https://www.youtube.com/watch?v=hcyuk4lfMlQ
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 .