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(mlgn) words of communication, compared with Floram's O(m√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.
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
author = {Adithya Vadapalli and Ryan Henry and Ian Goldberg},
title = {Duoram: A {Bandwidth-Efficient} Distributed {ORAM} for 2- and 3-Party Computation},
booktitle = {32nd USENIX Security Symposium (USENIX Security 23)},
year = {2023},
isbn = {978-1-939133-37-3},
address = {Anaheim, CA},
pages = {3907--3924},
url = {https://www.usenix.org/conference/usenixsecurity23/presentation/vadapalli},
publisher = {USENIX Association},
month = aug
}