[Resource Topic] 2018/364: Perfectly Secure Oblivious Parallel RAM

Welcome to the resource topic for 2018/364

Perfectly Secure Oblivious Parallel RAM

Authors: T-H. Hubert Chan, Kartik Nayak, Elaine Shi


We show that PRAMs can be obliviously simulated with perfect security, incurring only O(\log N \log \log N) blowup in parallel runtime, O(\log^3 N) blowup in total work, and O(1) blowup in space relative to the original PRAM. Our results advance the theoretical understanding of Oblivious (Parallel) RAM in several respects. First, prior to our work, no perfectly secure Oblivious Parallel RAM (OPRAM) construction was known; and we are the first in this respect. Second, even for the sequential special case of our algorithm (i.e., perfectly secure ORAM), we not only achieve logarithmic improvement in terms of space consumption relative to the state-of-the-art but also significantly simplify perfectly secure ORAM constructions. Third, our perfectly secure OPRAM scheme matches the parallel runtime of earlier statistically secure schemes with negligible failure probability. Since we remove the dependence (in performance) on the security parameter, our perfectly secure OPRAM scheme in fact asymptotically outperforms known statistically secure ones if (sub-)exponentially small failure probability is desired. Our techniques for achieving small parallel runtime are novel and we employ expander graphs to de-randomize earlier statistically secure schemes — this is the first time such techniques are used in the constructions of ORAMs/OPRAMs.

ePrint: https://eprint.iacr.org/2018/364

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 .