Welcome to the resource topic for 2020/604
Title:
Perfectly Oblivious (Parallel) RAM Revisited, and Improved Constructions
Authors: T-H. Hubert Chan, Elaine Shi, Wei-Kai Lin, Kartik Nayak
Abstract:Oblivious RAM (ORAM) is a technique for compiling any RAM 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 {\it parallel} RAM program to an oblivious counterpart. In this paper, we care about ORAM/OPRAM with {\it perfect security}, i.e., 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 O(\log^3 N/\log \log N) {\it expected} overhead. In comparison, prior literature has been stuck at O(\log^3 N) for more than a decade. Next, we show how to construct a perfect ORAM with O(\log^3 N/\log \log N) {\it deterministic} simulation overhead. We further show how to make the scheme parallel, resulting in an perfect OPRAM with O(\log^4 N/\log \log N) {\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 \sqrt{N} deterministic simulation overhead (Raskin and Simkin, Asiacrypt’19); moreover, their scheme works only for the sequential setting and is {\it not} amenable to parallelization. Finally, we additionally consider perfect ORAMs/OPRAMs whose performance bounds hold with high probability. For this new performance metric, we show new constructions whose simulation overhead is upper bounded by O(\log^3 /\log\log N) except with negligible in N probability, i.e., we prove high-probability performance bounds that match the expected bounds mentioned earlier.
ePrint: https://eprint.iacr.org/2020/604
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .