Welcome to the resource topic for 2024/011
Title:
MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier
Authors: Daniel Noble, Brett Hemenway Falk, Rafail Ostrovsky
Abstract: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.
ePrint: https://eprint.iacr.org/2024/011
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .