Oblivious RAM (ORAM) is a technique for compiling any 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 parallel program to an oblivious counterpart. In this paper, we care about ORAM/OPRAM with perfect security, i.e., the access patterns must identically distributed no matter what the program's memory request sequence is. We show two novel results.

The first result is a new perfectly secure OPRAM scheme with $O(\log^3 N/\log \log N)$ expected overhead. In comparison, the prior literature has been stuck at $O(\log^3 N)$ for more than a decade.

The second result is a new perfectly secure OPRAM scheme with $O(\log^4 N/\log \log N)$ worst-case overhead. To the best of our knowledge, this is the first perfectly secure OPRAM scheme with polylogarithmic worst-case overhead. Prior to our work, the state of the art is a perfectly secure ORAM scheme with more than $\sqrt{N}$ worst-case overhead, and the result does not generalize to a parallel setting. Our work advances the theoretical understanding of the asymptotic complexity of perfectly secure OPRAMs.