[Resource Topic] 2022/1747: Duoram: A Bandwidth-Efficient Distributed ORAM for 2- and 3-Party Computation

Welcome to the resource topic for 2022/1747

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

Authors: Adithya Vadapalli, Ryan Henry, Ian Goldberg


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.

ePrint: https://eprint.iacr.org/2022/1747

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 .