Paper 2021/1463

3-Party Distributed ORAM from Oblivious Set Membership

Brett Hemenway Falk, Daniel Noble, and 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 a novel 3-party semi-honest DORAM protocol with O((κ + D) log N) communication per access, where N is the size of the memory, κ is a security parameter and D is the block size. Our protocol performs polylogarithmic computation and does not require homomorphic encryption. Under natural parameter choices, this is the most communication-efficient DORAM with these properties. To build this DORAM protocol, we first present an extremely efficient oblivious data structure for answering set membership queries. From this we build an oblivious hash table with asymptotically optimal memory usage and access cost and with negligible failure probability. We believe these are of independent interest.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
distributed cryptographysecure multiparty computationsecret sharingoblivious ramdistributed oblivious ram
Contact author(s)
dgnoble @ cis upenn edu
History
2021-11-06: received
Short URL
https://ia.cr/2021/1463
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1463,
      author = {Brett Hemenway Falk and Daniel Noble and Rafail Ostrovsky},
      title = {3-Party Distributed ORAM from Oblivious Set Membership},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1463},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1463}},
      url = {https://eprint.iacr.org/2021/1463}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.