Welcome to the resource topic for 2023/1950
Title:
GigaDORAM: Breaking the Billion Address Barrier
Authors: Brett Falk, Rafail Ostrovsky, Matan Shtepel, Jacob Zhang
Abstract:We design and implement GigaDORAM, a novel
3-server Distributed Oblivious Random Access Memory (DORAM) protocol. Oblivious RAM allows a client to read and write to memory on an untrusted server while ensuring the server itself learns nothing about the client’s access pattern. Distributed Oblivious RAM (DORAM) allows a group of servers to efficiently access a secret-shared array at a secret-shared index.
A recent generation of DORAM implementations (e.g. FLORAM, DuORAM) has focused on building DORAM protocols based on Function Secret-Sharing (FSS). These protocols have low communication complexity and low round complexity but linear computational complexity of the servers. Thus, they work for moderate-size databases, but at a certain size, these FSS-based protocols become computationally inefficient.
In this work, we introduce GigaDORAM, a hierarchical-solution-based DORAM featuring poly-logarithmic computation and communication, but with an over 100\times reduction in rounds per query compared to previous hierarchical DORAM protocols. In our implementation, we show that for moderate to large databases where FSS-based solutions become computation-bound, our protocol is orders of magnitude more efficient than the best existing DORAM protocols. When N = 2^{31}, our DORAM is able to perform over 700 queries per second.
ePrint: https://eprint.iacr.org/2023/1950
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 .