View article

Oblivious RAM (ORAM) is a technique for compiling any RAM program to an oblivious counterpart, ie, 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}, ie, 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 {\it expected} overhead. In comparison, prior literature has been stuck at for more than a decade. Next, we show how to construct a perfect ORAM with {\it deterministic} simulation overhead. We further show how to make the scheme parallel, resulting in an perfect OPRAM with {\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 deterministic simulation overhead (Raskin and Simkin, Asiacrypt'19 …