Cryptology ePrint Archive: Report 2018/364

Perfectly Secure Oblivious Parallel RAM

T-H. Hubert Chan and Kartik Nayak and Elaine Shi

Abstract: 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.

Category / Keywords: cryptographic protocols / Oblivious RAM, Oblivious Parallel RAM

Original Publication (with minor differences): IACR-TCC-2018

Date: received 17 Apr 2018, last revised 2 Oct 2018

Contact author: kartik1507 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20181002:155559 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]