Paper 2018/364

Perfectly Secure Oblivious Parallel RAM

T-H. Hubert Chan, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2018
Keywords
Oblivious RAMOblivious Parallel RAM
Contact author(s)
kartik1507 @ gmail com
History
2018-10-02: revised
2018-04-18: received
See all versions
Short URL
https://ia.cr/2018/364
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/364,
      author = {T-H.  Hubert Chan and Kartik Nayak and Elaine Shi},
      title = {Perfectly Secure Oblivious Parallel RAM},
      howpublished = {Cryptology ePrint Archive, Paper 2018/364},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/364}},
      url = {https://eprint.iacr.org/2018/364}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.