[Resource Topic] 2023/578: DORAM revisited: Maliciously secure RAM-MPC with logarithmic overhead

Welcome to the resource topic for 2023/578

Title:
DORAM revisited: Maliciously secure RAM-MPC with logarithmic overhead

Authors: Brett Falk, Daniel Noble, Rafail Ostrovsky, Matan Shtepel, Jacob Zhang

Abstract:

Distributed Oblivious Random Access Memory (DORAM) is a secure multiparty protocol that allows a group of participants holding a secret-shared array to read and write to secret-shared locations within the array. The efficiency of a DORAM protocol is measured by the amount of communication and computation required per read/write query into the array. DORAM protocols are a necessary ingredient for executing Secure Multiparty Computation (MPC) in the RAM model.

Although DORAM has been widely studied, all existing DORAM protocols have focused on the setting where the DORAM servers are semi-honest. Generic techniques for upgrading a semi-honest DORAM protocol to the malicious model typically increase the asymptotic communication complexity of the DORAM scheme.

In this work, we present a 3-party DORAM protocol which requires O((\kappa + D)\log N) communication and computation per query, for a database of size N with D-bit values, where \kappa is the security parameter. Our hidden constants in a big-O nation are small. We show that our protocol is UC-secure in the presence of a malicious, static adversary. This matches the communication and computation complexity of the best semi-honest DORAM protocol, and is the first malicious DORAM protocol with this complexity.

ePrint: https://eprint.iacr.org/2023/578

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 .