Paper 2014/594

Oblivious Parallel RAM

Elette Boyle and Kai-Min Chung and Rafael Pass

Abstract

A machine is said to be {\em oblivious} if the sequences of memory accesses made by the machine for two inputs with the same running time are identically (or close to identically) distributed. Oblivious RAM (ORAM) compilers -- compilers that turn any RAM program $\Pi$ into an oblivious RAM $\Pi'$, while incurring only a "small", polylogarithmic, slow-down -- have been extensively studied since the work of Goldreich and Ostrovsky (JACM 1996), and have numerous fundamental applications. These compilers, however, do not leverage parallelism: even if $\Pi$ can be heavily parallelized, $\Pi'$ will be inherently sequential. In this work, we present the first {\em Oblivious Parallel RAM (OPRAM)} compiler, which compiles any PRAM into an oblivious PRAM while incurring only a polylogarithmic slowdown.