Paper 2016/1084

Circuit OPRAM: Unifying Statistically and Computationally Secure ORAMs and OPRAMs

T-H. Hubert Chan and Elaine Shi


An Oblivious Parallel RAM (OPRAM) provides a general method to simulate any Parallel RAM (PRAM) program, such that the resulting memory access patterns leak nothing about secret inputs. OPRAM was originally proposed by Boyle et al. as the natural parallel counterpart of Oblivious RAM (ORAM), which was shown to have broad applications, e.g., in cloud outsourcing, secure processor design, and secure multi-party computation. Since parallelism is common in modern computing architectures such as multi-core processors or cluster computing, OPRAM is naturally a powerful and desirable building block as much as its sequential counterpart ORAM is. Although earlier works have shown how to construct OPRAM schemes with polylogarithmic simulation overhead, in comparison with best known sequential ORAM constructions, all existing OPRAM schemes are (poly-)logarithmic factors more expensive. In this paper, we present a new framework in which we construct both statistically secure and computationally secure OPRAM schemes whose asymptotical performance matches the best known ORAM schemes in each setting. Since an OPRAM scheme with simulation overhead X directly implies an ORAM scheme with simulation overhead X, our result can be regarded as providing a unifying framework in which we can subsume all known results on statistically and computationally secure ORAMs and OPRAMs alike. Particularly for the case of OPRAMs, we also improve the state-of-the-art scheme by superlogarithmic factors. To achieve the aforementioned results requires us to combine a variety of techniques involving 1) efficient parallel oblivious algorithm design; and 2) designing tight randomized algorithms and proving measure concentration bounds about the rather involved stochastic process induced by the OPRAM algorithm.

Available format(s)
Publication info
Preprint. MINOR revision.
Oblivious RAMparallel algorithmPRAM
Contact author(s)
runting @ gmail com
2020-07-05: last of 7 revisions
2016-11-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {T-H.  Hubert Chan and Elaine Shi},
      title = {Circuit {OPRAM}: Unifying Statistically and Computationally Secure {ORAMs} and {OPRAMs}},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1084},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.