Paper 2024/011

MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication

Abstract

A Distributed Oblivious RAM is a multi-party protocol that securely implements a RAM functionality on secret-shared inputs and outputs. This paper presents two DORAMs in the semi-honest honest-majority 3-party setting which are information-theoretically secure and whose communication costs are asymptotic improvements over previous work. Let $n$ be the number of memory locations and let $d$ be the bit-length of each location. The first, MetaDORAM1, is \emph{statistically} secure, with $n^{-\omega(1)}$ leakage. It has $O(\log_b(n) d + b \omega(1) \log(n) + \log^3(n)/\log(\log(n)))$ bits of communication per memory access. Here, $b \geq 2$ is a free parameter and $\omega(1)$ is any super-constant function (in $n$). The best prior work was that of Abraham et al (PKC 2017), which has cost $O(\log_b(n) d + b \omega(1) \log_b(n) \log^2(n))$. MetaDORAM1 is an asymptotic improvement over the work of Abraham et al whenever $d = O(\log^2(n))$. The second protocol, MetaDORAM2, achieves \emph{perfect} security, albeit at the cost of a computationally-expensive setup phase. It has communication cost $O(\log_b(n)d + b \log(n) + \log^3(n)/\log(\log(n)))$. The best prior work of Chan et al (ASIACRYPT 2018) has communication cost $O(\log(n) d + \log^3(n))$. When $b = \log(n)$, the communication cost of our protocol is $O(\log(n) d /\log(\log(n)) + \log^3(n)/\log(\log(n)))$, that is a $\Theta(\log(\log(n)))$ factor improvement over that of Chan et al. Our work is the first perfectly secure DORAM with sub-logarithmic communication overhead. This comes at the cost of a once-off (for any given $n$) setup phase which requires exponential (in $n$) computation. By a trivial transformation, these can be transformed, respectively, into statistically and perfectly secure active multi-server ORAM protocols with the same communication costs. These multi-server ORAM protocols are likewise asymptotic improvements over the state of the art.

Note: The paper has been modified to emphasize the contribution of the first perfectly secure DORAM with sub-logarithmic communication overhead. It has also been modified to allow for a free parameter, $b$, which allows balancing of the asymptotic terms, dependent on the block-size $d$.