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

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), DUO-RAM 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 dataindependent preprocessing phase, leaving just O(m) words of online communication cost for the sequence-i.e., a constant online communication cost per memory access. * An extended version of this paper is available [28]. O(lgn) ory D ∈ 0, 1 n×w consisting of n words that are each w bits long. We denote the word at memory address i in D by D[i] ∈ 0, 1 w . Depending on the type of memory access being performed, the computation parties hold either an encrypted copy of D (when reading) or a secret shared copy of D (when writing); a "refresh" operation converts D from its secret-shared representation to its encrypted one. FLORAM also makes use of a "stash" (the details of which we gloss over) to reduce the frequency with which the computation parties must invoke the (rather costly) refresh operation, resulting in a lower amortized cost per memory access. Oblivious reads in FLORAM. Computation parties P 0 and P 1 hold symmetric keys k 0 and k 1 respectively alongside the memory D blinded using a pseudorandom function F; i.e., P 0 and P 1 hold in common blinded memory D ∈ 0, 1 n×w such that D Given shares of a target address i * ∈ [0..n), they obtain shares of the corresponding word D[i * ] using simple PIR followed by an oblivious unblinding step, as follows: