Paper 2015/1053

Oblivious Parallel RAM: Improved Efficiency and Generic Constructions

Binyi Chen, Huijia Lin, and Stefano Tessaro

Abstract

Oblivious RAM (ORAM) garbles read/write operations by a client (to access a remote storage server or a random-access memory) so that an adversary observing the garbled access sequence cannot infer any information about the original operations, other than their overall number. This paper considers the natural setting of Oblivious Parallel RAM (OPRAM) recently introduced by Boyle, Chung, and Pass (TCC 2016A), where $m$ clients simultaneously access in parallel the storage server. The clients are additionally connected via point-to-point links to coordinate their accesses. However, this additional inter-client communication must also remain oblivious. The main contribution of this paper is twofold: We construct the first OPRAM scheme that (nearly) matches the storage and server-client communication complexities of the most efficient single-client ORAM schemes. Our scheme is based on an extension of Path-ORAM by Stefanov et al (CCS 2013). Moreover, we present a generic transformation turning any (single-client) ORAM scheme into an OPRAM scheme.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCC 2016
Keywords
Cryptographic ProtocolsOblivious RAM
Contact author(s)
tessaro @ cs ucsb edu
rachel lin @ cs ucsb edu
binyichen @ umail ucsb edu
History
2015-10-30: received
Short URL
https://ia.cr/2015/1053
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1053,
      author = {Binyi Chen and Huijia Lin and Stefano Tessaro},
      title = {Oblivious Parallel RAM: Improved Efficiency and Generic Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1053},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1053}},
      url = {https://eprint.iacr.org/2015/1053}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.