Oblivious Parallel RAM.
Elette Boyle, Kai-Min Chung, Rafael Pass · IACR Cryptology ePrint Archive · 2014
A machine is said to be 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 into a oblivious RAM 0 , while only incurring a \small, polylogarithmic, slow-down|have been extensively studied since the work of Goldreich and Ostrovsky [GO96] and have numerous fundamental applications. These compilers, however, do not leverage parallelism: even if can be heavily parallelized, 0 will be inherently sequential. In this work, we present the rst Oblivious Parallel RAM (OPRAM) compiler, which compiles any PRAM into an oblivious PRAM while only incurring a polylogarithmic slowdown.