Paper 2018/706

Efficient 3-Party Distributed ORAM

Paul Bunn, Jonathan Katz, Eyal Kushilevitz, and Rafail Ostrovsky

Abstract

Distributed Oblivious RAM (DORAM) protocols---in which parties obliviously access a shared location in a shared array---are a fundamental component of secure-computation protocols in the RAM model. We show here an efficient, 3-party DORAM protocol with semi-honest security for a single corrupted party. To the best of our knowledge, ours is the first protocol for this setting that runs in constant rounds, requires sublinear communication and linear work, and makes only black-box use of cryptographic primitives. We believe our protocol is also concretely more efficient than existing solutions. As a building block of independent interest, we construct a 3-server distributed point function with security against two colluding servers that is simpler and has better concrete efficiency than prior work.

Note: Protocols have been improved, and proofs have been added.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
ORAMsecure computation
Contact author(s)
jkatz @ cs umd edu
History
2018-08-16: revised
2018-08-01: received
See all versions
Short URL
https://ia.cr/2018/706
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/706,
      author = {Paul Bunn and Jonathan Katz and Eyal Kushilevitz and Rafail Ostrovsky},
      title = {Efficient 3-Party Distributed {ORAM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/706},
      year = {2018},
      url = {https://eprint.iacr.org/2018/706}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.