Paper 2023/1950

GigaDORAM: Breaking the Billion Address Barrier

Brett Falk, University of Pennsylvania
Rafail Ostrovsky, University of California, Los Angeles
Matan Shtepel, University of Pennsylvania, University of California, Los Angeles
Jacob Zhang, University of California, Los Angeles
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)
PDF
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
No rights reserved
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.