Cryptology ePrint Archive: Report 2017/861

On the Depth of Oblivious Parallel RAM

T-H. Hubert Chan and 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.

Category / Keywords: oblivious parallel RAM

Original Publication (with major differences): ASIACRYPT 2017

Date: received 4 Sep 2017, last revised 9 Sep 2017

Contact author: tszhubert at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170909:232558 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]