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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- perfect oblivious RAMoblivious PRAM
- Contact author(s)
- hubert @ cs hku hk,wklin @ cs cornell edu,kartik @ cs duke edu,runting @ gmail com
- History
- 2021-05-12: last of 3 revisions
- 2020-05-22: received
- See all versions
- Short URL
- https://ia.cr/2020/604
- License
-
CC BY