International Association
for Cryptologic Research

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.