Paper 2017/861

On the Depth of Oblivious Parallel RAM

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


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.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.ASIACRYPT 2017
oblivious parallel RAM
Contact author(s)
tszhubert @ gmail com
2017-09-09: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.