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.