Perfectly Secure Oblivious Parallel RAM

Conference Paper

We show that PRAMs can be obliviously simulated with perfect security, incurring only blowup in parallel runtime, 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 special expander graphs to derandomize earlier statistically secure OPRAM techniques—this is the first time such techniques are used in the constructions of ORAMs/OPRAMs.

Full Text

Duke Authors

Cited Authors

  • Chan, THH; Nayak, K; Shi, E

Published Date

  • January 1, 2018

Published In

Volume / Issue

  • 11240 LNCS /

Start / End Page

  • 636 - 668

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783030038090

Digital Object Identifier (DOI)

  • 10.1007/978-3-030-03810-6_23

Citation Source

  • Scopus