International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 03 August 2014

Elette Boyle, Kai-Min Chung, Rafael Pass
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.