Grotto: Screaming fast (2 + 1)-PC for Z via (2, 2)-DPFs
Published in 30th ACM Conference on Computer and Communications Security (CCS), 2023
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 addressable locations, Duoram can perform a sequence of arbitrarily interleaved reads and writes using just words of communication, compared with Floram’s words. Moreover, most of this work can occur during a data-independent preprocessing phase, leaving just words of online communication cost for the sequence—i.e., a constant online communication cost per memory access.