IACR News item: 22 May 2020
T-H. Hubert Chan, Wei-Kai Lin, Kartik Nayak, Elaine Shi
ePrint Report
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.
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.
Additional news items may be found on the IACR news page.