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.
Category / Keywords: cryptographic protocols / Distributed Oblivious RAM, Square Root ORAM, Doubly Efficient PIR, Secure Multi- Party Computation, Fast Fourier Transform Date: received 11 Dec 2020 Contact author: arihamlin at gmail com Available format(s): PDF | BibTeX Citation Version: 20201213:165919 (All versions of this report) Short URL: ia.cr/2020/1547