Oblivious Parallel RAM (OPRAM) is a natural extension of ORAM to the (more realistic) parallel setting where several processors make concurrent accesses to a shared memory. It is known that any OPRAM must incur logarithmic work overhead and for highly parallel RAMs a logarithmic depth blowup (in the balls and bins model). Despite the significant recent advances, there is still a large gap: all existing OPRAM schemes incur a poly-logarithmic overhead either in total work or in depth.
Our main result closes the aforementioned gap and provides an essentially optimal OPRAM scheme. Specifically, assuming one-way functions, we show that any Parallel RAM with memory capacity~$N$ can be obliviously simulated in space $O(N)$, incurring only $O(\log N)$ blowup in (amortized) total work as well as in depth. Our transformation supports all PRAMs in the CRCW mode and the resulting simulation is in the CRCW mode as well.
Category / Keywords: cryptographic protocols / oblivious RAM, PRAM Date: received 16 Oct 2020 Contact author: Gilad Asharov at biu ac il,ilankom10@gmail com,wl572@cornell edu,enoch@dei unipd it,runting@gmail com Available format(s): PDF | BibTeX Citation Version: 20201019:073250 (All versions of this report) Short URL: ia.cr/2020/1292