International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Mayank Varia

Publications

Year
Venue
Title
2021
PKC
Two-server Distributed ORAM with Sublinear Computation and Constant Rounds 📺
Ariel Hamlin 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 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.
2017
PKC
2010
TCC
2010
TCC
2009
TCC

Program Committees

Crypto 2022