DORAM revisited: Maliciously secure RAM-MPC with logarithmic overhead

Brett Falk; Daniel Noble; Rafail Ostrovsky; Matan Shtepel; Jacob Zhang

Paper 2023/578

DORAM revisited: Maliciously secure RAM-MPC with logarithmic overhead

Brett Falk, University of Pennsylvania

Daniel Noble, University of Pennsylvania

Rafail Ostrovsky, University of California, Los Angeles

Matan Shtepel, University of California, Los Angeles

Jacob Zhang, University of California, Los Angeles

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.

Note: Add concurrent work subsection.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in TCC 2023
Keywords: MPC ORAM DORAM RAM-MPC UC
Contact author(s): fbrett @ cis upenn edu
danielnoble @ protonmail com
rafail @ cs ucla edu
matan shtepel @ ucla edu
Jacob b zhang @ gmail com
History: 2023-12-23: last of 2 revisions; 2023-04-24: received; See all versions
Short URL: https://ia.cr/2023/578
License: CC BY

BibTeX

@misc{cryptoeprint:2023/578,
      author = {Brett Falk and Daniel Noble and Rafail Ostrovsky and Matan Shtepel and Jacob Zhang},
      title = {DORAM revisited: Maliciously secure RAM-MPC with logarithmic overhead},
      howpublished = {Cryptology ePrint Archive, Paper 2023/578},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/578}},
      url = {https://eprint.iacr.org/2023/578}
}