Paper 2023/1950
GigaDORAM: Breaking the Billion Address Barrier
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.
Note: Fixing USENIX badges.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. USENIX Security 2023
- Keywords
- DORAMMPCORAMRAM-MPC
- Contact author(s)
-
fbrett @ cis upenn edu
rafail @ cs ucla edu
matan shtepel @ gmail com
jacob b zhang @ gmail com - History
- 2024-01-04: revised
- 2023-12-23: received
- See all versions
- Short URL
- https://ia.cr/2023/1950
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/1950, author = {Brett Falk and Rafail Ostrovsky and Matan Shtepel and Jacob Zhang}, title = {{GigaDORAM}: Breaking the Billion Address Barrier}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1950}, year = {2023}, url = {https://eprint.iacr.org/2023/1950} }