CryptoDB
Two-server Distributed ORAM with Sublinear Computation and Constant Rounds
| Authors: | |
|---|---|
| Download: | |
| 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 the 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 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^e) for any e > 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 multi- variate polynomials based on the Fast Fourier Transform, which may be of independent interest. |
Video from PKC 2021
BibTeX
@article{pkc-2021-30991,
title={Two-server Distributed ORAM with Sublinear Computation and Constant Rounds},
booktitle={Public-Key Cryptography - PKC 2021},
publisher={Springer},
doi={10.1007/978-3-030-75248-4_18},
author={Ariel Hamlin and Mayank Varia},
year=2021
}