MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier

ePrint Report: MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier

Daniel Noble, Brett Hemenway Falk, Rafail Ostrovsky

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 …

bits breaking communication computational daniel distributed eprint report information log memory oblivious protocol report