### Optimal Oblivious Parallel RAM

Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi

##### Abstract

An oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (STOC '87 and J. ACM '96), is a technique for hiding RAM's access pattern. That is, for every input the distribution of the observed locations accessed by the machine is essentially independent of the machine's secret inputs. Recent progress culminated in a work of Asharov et al. (EUROCRYPT '20), obtaining an ORAM with (amortized) logarithmic overhead in total work, which is known to be optimal. 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.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. SODA 2022
DOI
10.1137/1.9781611977073.98
Keywords
oblivious RAMPRAM
Contact author(s)
Gilad Asharov @ biu ac il
ilankom10 @ gmail com
wl572 @ cornell edu
enoch @ dei unipd it
runting @ gmail com
History
2022-03-27: last of 2 revisions
See all versions
Short URL
https://ia.cr/2020/1292

CC BY

BibTeX

@misc{cryptoeprint:2020/1292,
author = {Gilad Asharov and Ilan Komargodski and Wei-Kai Lin and Enoch Peserico and Elaine Shi},
title = {Optimal Oblivious Parallel RAM},
howpublished = {Cryptology ePrint Archive, Paper 2020/1292},
year = {2020},
doi = {10.1137/1.9781611977073.98},
note = {\url{https://eprint.iacr.org/2020/1292}},
url = {https://eprint.iacr.org/2020/1292}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.