Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Oblivious RAM

Date: received 2 Aug 2014

Contact author: eboyle at alum mit edu

Available format(s): PDF | BibTeX Citation

Version: 20140803:215104 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]