Paper 2020/1547

Two-server Distributed ORAM with Sublinear Computation and Constant Rounds

Ariel Hamlin and Mayank Varia


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Distributed Oblivious RAMSquare Root ORAMDoubly Efficient PIRSecure Multi- Party ComputationFast Fourier Transform
Contact author(s)
arihamlin @ gmail com
2020-12-13: received
Short URL
Creative Commons Attribution


      author = {Ariel Hamlin and Mayank Varia},
      title = {Two-server Distributed ORAM with Sublinear Computation and Constant Rounds},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1547},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.