Paper 2017/861

On the Depth of Oblivious Parallel RAM

T-H. Hubert Chan, Kai-Min Chung, and Elaine Shi

Abstract

Oblivious Parallel RAM (OPRAM), first proposed by Boyle, Chung, and Pass, is the natural parallel extension of Oblivious RAM (ORAM). OPRAM provides a powerful cryptographic building block for hiding the access patterns of programs to sensitive data, while preserving the paralellism inherent in the original program. All prior OPRAM schemes adopt a single metric of ``simulation overhead'' that characterizes the blowup in parallel runtime, assuming that oblivious simulation is constrained to using the same number of CPUs as the original PRAM. In this paper, we ask whether oblivious simulation of PRAM programs can be further sped up if the OPRAM is allowed to have more CPUs than the original PRAM. We thus initiate a study to understand the true depth of OPRAM schemes (i.e., when the OPRAM may have access to unbounded number of CPUs). On the upper bound front, we construct a new OPRAM scheme that gains a logarithmic factor in depth and without incurring extra blowup in total work in comparison with the state-of-the-art OPRAM scheme. On the lower bound side, we demonstrate fundamental limits on the depth any OPRAM scheme --- even when the OPRAM is allowed to have an unbounded number of CPUs and blow up total work arbitrarily. We further show that our upper bound result is optimal in depth for a reasonably large parameter regime that is of particular interest in practice.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. ASIACRYPT 2017
Keywords
oblivious parallel RAM
Contact author(s)
tszhubert @ gmail com
History
2017-09-09: received
Short URL
https://ia.cr/2017/861
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/861,
      author = {T-H.  Hubert Chan and Kai-Min Chung and Elaine Shi},
      title = {On the Depth of Oblivious Parallel {RAM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/861},
      year = {2017},
      url = {https://eprint.iacr.org/2017/861}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.