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 $$ be the number of memory locations and let $$ be the bit-length of each location. The first, MetaDORAM1, is \emph{statistically} secure, with $$ leakage. It has $$ bits of communication per memory access. Here, $$ is a free parameter and $$ is any super-constant function (in $$). The best prior work was that of Abraham et al (PKC 2017), which has cost $$. MetaDORAM1 is an asymptotic improvement over the work of Abraham et al whenever $$. The second protocol, MetaDORAM2, achieves \emph{perfect} security, albeit at the cost of a computationally-expensive setup phase. It has communication cost $$. The best prior work of Chan et al (ASIACRYPT 2018) has communication cost $$. When $$, the communication cost of our protocol is $$, that is a $$ 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 $$) setup phase which requires exponential (in $$) 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, $$, which allows balancing of the asymptotic terms, dependent on the block-size $$.