Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-005 | 24th January 2024 18:06

MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier

RSS-Feed




Revision #1
Authors: Daniel Noble, Brett Hemenway, Rafail Ostrovsky
Accepted on: 24th January 2024 18:06
Downloads: 21
Keywords: 


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.



Changes to previous version:

Updating acks.


Paper:

TR24-005 | 4th January 2024 00:16

MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier





TR24-005
Authors: Daniel Noble, Brett Hemenway, Rafail Ostrovsky
Publication: 14th January 2024 08:30
Downloads: 88
Keywords: 


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.



ISSN 1433-8092 | Imprint