Paper 2020/604

Perfectly Secure Oblivious Parallel RAM with $O(\log^3 N/ \log \log N)$ Overhead

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

Abstract

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.