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

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.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2023
Contact author(s)
fbrett @ cis upenn edu
danielnoble @ protonmail com
rafail @ cs ucla edu
matan shtepel @ ucla edu
Jacob b zhang @ gmail com
2023-12-23: last of 2 revisions
2023-04-24: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.