Paper 2024/011

MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication

Abstract

This paper presents a Distributed Oblivious RAM (DORAM) protocol, MetaDORAM, that is information-theoretically secure and has lower communication cost than all previous info-theoretically secure DORAM protocols for small block sizes. Specifically, given a memory of $n$ locations, each of size $d$ bits, MetaDORAM requires only $O( (d+\log^2(n)) \log(n)/\log(\log(n)) )$ bits of communication per query. When $d = \Theta(\log^2(n))$, this is a $\Theta(\log(n)/\log \log(n))$ \emph{overhead}, compared to the cost of reading one memory location directly. By comparison, the only existing statistically secure DORAM with sub-logarithmic overhead has communication cost $O( \log_a(n) d + a \omega(1) \log^2(n) \log_a(n))$ (Abraham et al. PKC '17), where $\omega(1)$ is any super-constant function in $n$ and $a \geq 2$ is a free parameter. MetaDORAM obtains sub-logarithmic communication overhead for smaller block sizes than previously achieved (any $d = \omega(\log^2(n)/\log(\log(n)))$) while providing statistical security, i.e., no computational assumptions. We circumvent the Goldreich-Ostrovsky lower bound by allowing servers to perform poly(log(n)) work, but without computational assumptions. By a standard transformation, our protocol also implies a 3-server active ORAM, Meta3ORAM, with information-theoretic security and $O( (d+\log^2(n)) \log(n)/\log(\log(n)) )$ communication per query. For small $d$, this is lower than all previous statistically-secure multi-server ORAMs. MetaDORAM and Meta3ORAM also have low communication costs relative to DORAM and multi-server ORAM protocols which make use of computational assumptions. Even compared to several recent works that make use of $O(n)$ computation, our protocols have lower communication cost. Our protocols are secure in the semi-honest honest-majority setting. We also show that perfectly secure DORAM/multi-server ORAM with the same efficiency can be obtained using a computationally-expensive once-off setup phase.

Note: In the initial submission, the authors were unaware that (Abraham et al, PKC '17) had previously created a sub-log overhead statistically-secure multi-server ORAM/DORAM. The paper now presents its contributions with this work in mind.