Paper 2014/594

Oblivious Parallel RAM and Applications

Elette Boyle, Kai-Min Chung, and Rafael Pass

Abstract

We initiate the study of cryptography for parallel RAM (PRAM) programs. The PRAM model captures modern multi-core architectures and cluster computing models, where several processors execute in parallel and make accesses to shared memory, and provides the “best of both” circuit and RAM models, supporting both cheap random access and parallelism. We propose and attain the notion of Oblivious PRAM. We present a compiler taking any PRAM into one whose distribution of memory accesses is statistically independent of the data (with negligible error), while only incurring a polylogarithmic slowdown (in both total and parallel complexity). We discuss applications of such a compiler, building upon recent advances relying on Oblivious (sequential) RAM (Goldreich Ostrovsky JACM’12). In particular, we demonstrate the construction of a garbled PRAM compiler based on an OPRAM compiler and secure identity-based encryption.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Oblivious RAM
Contact author(s)
eboyle @ alum mit edu
History
2015-08-31: revised
2014-08-03: received
See all versions
Short URL
https://ia.cr/2014/594
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/594,
      author = {Elette Boyle and Kai-Min Chung and Rafael Pass},
      title = {Oblivious Parallel RAM and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2014/594},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/594}},
      url = {https://eprint.iacr.org/2014/594}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.