Paper 2022/1747

Duoram: A Bandwidth-Efficient Distributed ORAM for 2- and 3-Party Computation

Adithya Vadapalli, University of Waterloo
Ryan Henry, University of Calgary
Ian Goldberg, University of Waterloo
Abstract

We design, analyze, and implement Duoram, a fast and bandwidth-efficient distributed ORAM protocol suitable for secure 2- and 3-party computation settings. Following Doerner and shelat's Floram construction (CCS 2017), Duoram leverages (2,2)-distributed point functions (DPFs) to represent PIR and PIR-writing queries compactly—but with a host of innovations that yield massive asymptotic reductions in communication cost and notable speedups in practice, even for modestly sized instances. Specifically, Duoram introduces a novel method for evaluating dot products of certain secret-shared vectors using communication that is only logarithmic in the vector length. As a result, for memories with $n$ addressable locations, Duoram can perform a sequence of $m$ arbitrarily interleaved reads and writes using just $O(m\lg n)$ words of communication, compared with Floram's $O(m \sqrt{n})$ words. Moreover, most of this work can occur during a data-independent preprocessing phase, leaving just $O(m)$ words of online communication cost for the sequence—i.e., a constant online communication cost per memory access.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. USENIX Security 2023
Keywords
multiparty computationdistributed point functionsoblivious RAM
Contact author(s)
avadapal @ uwaterloo ca
ryan henry @ ucalgary ca
iang @ uwaterloo ca
History
2023-02-26: revised
2022-12-19: received
See all versions
Short URL
https://ia.cr/2022/1747
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1747,
      author = {Adithya Vadapalli and Ryan Henry and Ian Goldberg},
      title = {Duoram: A Bandwidth-Efficient Distributed ORAM for 2- and 3-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1747},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1747}},
      url = {https://eprint.iacr.org/2022/1747}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.