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.

The following changes have been made:
- We were previously unaware of the the work of Abraham et al (PKC 2017) which introduced a statistically secure DORAM with sublogarithmic overhead. We have added recognition of this paper and removed any claims of being the first sub-logarithmic statistically secure DORAM.
- A free parameter, $b$, has been introduced which allows asymptotic terms to be balanced according to the block-size, $d$.
- The paper now highlights that a perfectly secure variant is possible, making the contribution the first perfectly secure DORAM with sub-logarithmic communication overhead.

This paper presents the first Distributed Oblivious RAM (DORAM) protocol that achieves sub-logarithmic communication overhead without computational assumptions.
That is, given $n$ $d$-bit memory locations, we present an information-theoretically secure protocol which requires $o(d \cdot \log(n))$ bits of communication per access (when $d = \Omega(\log^2(n)$).

This comes as a surprise, since the Goldreich-Ostrovsky lower bound shows that the related problem of Oblivious RAMs requires logarithmic overhead in the number of memory locations accessed. It was shown that this bound also applies in the multi-server ORAM setting, and therefore also applies in the DORAM setting. Achieving sub-logarithmic communication therefore requires accessing and using $\Omega(\log(n) \cdot d)$ bits of memory, without engaging in communication for each bit accessed. Techniques such as Fully Homomorphic Encryption and Function Secret Sharing allow secure selection of the relevant memory locations with small communication overhead, but introduce computational assumptions.

In this paper we show that it is possible to avoid a logarithmic communication overhead even without any computational assumptions.
Concretely, we present a 3-party honest-majority DORAM that is secure against semi-honest adversaries. The protocol has communication cost $$\Theta\left((\log^2(n) + d) \cdot \frac{\log(n)}{\log(\log(n)}\right)$$ For any $d = \Omega(\log^2(n))$ the overhead is therefore $\Theta(\log(n)/\log(\log(n)))$. Additionally, we show a subtle flaw in a common approach for analyzing the security of Oblivious Hash Tables.
We prove our construction secure using an alternative approach.

Updating acks.

This paper presents the first Distributed Oblivious RAM (DORAM) protocol that achieves sub-logarithmic communication overhead without computational assumptions.
That is, given $n$ $d$-bit memory locations, we present an information-theoretically secure protocol which requires $o(d \cdot \log(n))$ bits of communication per access (when $d = \Omega(\log^2(n)$).

This comes as a surprise, since the Goldreich-Ostrovsky lower bound shows that the related problem of Oblivious RAMs requires logarithmic overhead in the number of memory locations accessed. It was shown that this bound also applies in the multi-server ORAM setting, and therefore also applies in the DORAM setting. Achieving sub-logarithmic communication therefore requires accessing and using $\Omega(\log(n) \cdot d)$ bits of memory, without engaging in communication for each bit accessed. Techniques such as Fully Homomorphic Encryption and Function Secret Sharing allow secure selection of the relevant memory locations with small communication overhead, but introduce computational assumptions.

In this paper we show that it is possible to avoid a logarithmic communication overhead even without any computational assumptions.
Concretely, we present a 3-party honest-majority DORAM that is secure against semi-honest adversaries. The protocol has communication cost $$\Theta\left((\log^2(n) + d) \cdot \frac{\log(n)}{\log(\log(n)}\right)$$ For any $d = \Omega(\log^2(n))$ the overhead is therefore $\Theta(\log(n)/\log(\log(n)))$. Additionally, we show a subtle flaw in a common approach for analyzing the security of Oblivious Hash Tables.
We prove our construction secure using an alternative approach.