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

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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. USENIX Security 2023
multiparty computationdistributed point functionsoblivious RAM
Contact author(s)
avadapal @ uwaterloo ca
ryan henry @ ucalgary ca
iang @ uwaterloo ca
2023-02-26: revised
2022-12-19: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.