Paper 2020/604

Perfectly Oblivious (Parallel) RAM Revisited, and Improved Constructions

T-H. Hubert Chan, Elaine Shi, Wei-Kai Lin, and Kartik Nayak


Oblivious RAM (ORAM) is a technique for compiling any RAM program to an oblivious counterpart, i.e., one whose access patterns do not leak information about the secret inputs. Similarly, Oblivious Parallel RAM (OPRAM) compiles a {\it parallel} RAM program to an oblivious counterpart. In this paper, we care about ORAM/OPRAM with {\it perfect security}, i.e., the access patterns must be {\it identically distributed} no matter what the program's memory request sequence is. In the past, two types of perfect ORAMs/OPRAMs have been considered: constructions whose performance bounds hold {\it in expectation} (but may occasionally run more slowly); and constructions whose performance bounds hold {\it deterministically} (even though the algorithms themselves are randomized). In this paper, we revisit the performance metrics for perfect ORAM/OPRAM, and show novel constructions that achieve asymptotical improvements for all performance metrics. Our first result is a new perfectly secure OPRAM scheme with $O(\log^3 N/\log \log N)$ {\it expected} overhead. In comparison, prior literature has been stuck at $O(\log^3 N)$ for more than a decade. Next, we show how to construct a perfect ORAM with $O(\log^3 N/\log \log N)$ {\it deterministic} simulation overhead. We further show how to make the scheme parallel, resulting in an perfect OPRAM with $O(\log^4 N/\log \log N)$ {\it deterministic} simulation overhead. For perfect ORAMs/OPRAMs with deterministic performance bounds, our results achieve {\it subexponential} improvement over the state-of-the-art. Specifically, the best known prior scheme incurs more than $\sqrt{N}$ deterministic simulation overhead (Raskin and Simkin, Asiacrypt'19); moreover, their scheme works only for the sequential setting and is {\it not} amenable to parallelization. Finally, we additionally consider perfect ORAMs/OPRAMs whose performance bounds hold with high probability. For this new performance metric, we show new constructions whose simulation overhead is upper bounded by $O(\log^3 /\log\log N)$ except with negligible in $N$ probability, i.e., we prove high-probability performance bounds that match the expected bounds mentioned earlier.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ITC 2021
perfect oblivious RAMoblivious PRAM
Contact author(s)
hubert @ cs hku hk
wklin @ cs cornell edu
kartik @ cs duke edu
runting @ gmail com
2021-05-12: last of 3 revisions
2020-05-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {T-H.  Hubert Chan and Elaine Shi and Wei-Kai Lin and Kartik Nayak},
      title = {Perfectly Oblivious (Parallel) {RAM} Revisited, and Improved Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2020/604},
      year = {2020},
      doi = {10.4230/LIPIcs.ITC.2021.9},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.