3-Party Distributed ORAM from Oblivious Set Membership
Brett Hemenway Falk, Daniel Noble, Rafail Ostrovsky
Abstract:
Distributed Oblivious RAM (DORAM) protocols allow a group of participants to obliviously access a secret-shared array at a secret-shared index, and DORAM is the key tool for secure multiparty computation (MPC) in the RAM model.
In this work we present an efficient DORAM protocol with \(O((\kappa + D) \log N)\) communication per access, where N is the size of the memory, \(\kappa \) is a security parameter and D is the block size.
Our DORAM protocol is secure in the 3-party honest-majority setting, and is built from two novel, efficient components.
The first is a novel data structure for answering set membership queries. This data structure has asymptotically optimal (with tiny constants) memory usage, lookup cost and negligible failure probability. We show how this data structure can also be efficiently instantiated under MPC. The second is a Distributed Oblivious Hash Table protocol (in the 3-party honesty-majority setting) with asymptotically optimal memory usage and \(O(\kappa + D)\) communication per access. To our knowledge, this is the first Distributed Oblivious Hash Table with this efficiency that does not use homomorphic encryption.
Finally, we use this to build the aforementioned DORAM protocol. Our protocol performs polylogarithmic computation and does not require homomorphic encryption. Under natural parameter choices, it is the most communication-efficient DORAM with these properties.
comment:
SCN 2022: 437-461
Fetch PDF file of the paper