Paper 2015/1068

Black-Box Parallel Garbled RAM

Steve Lu and Rafail Ostrovsky

Abstract

In 1982, Yao introduced a fundamental technique of ``circuit garbling'' that became a central building block in cryptography. Recently, the question of garbling general random-access memory (RAM) programs received a lot of attention in the literature where garbling an encrypted data can be done separately from garbling program(s) that execute on this (garbled) RAM. The most recent results of Garg, Lu, and Ostrovsky (FOCS 2015) achieve a garbled RAM with black-box use of any one-way functions and poly-log overhead of data and program garbling in all the relevant parameters, including program run-time. The advantage of their solution is that large data can be garbled first, and act as persistent garbled storage (e.g. in the cloud) and later programs can be garbled and sent to be executed on this garbled database in a non-interactive manner. One of the main advantages of cloud computing is not only that it has large storage but also that it has a large number of parallel processors. Despite multiple successful efforts on parallelizing (interactive) Oblivious RAM, the non-interactive garbling of parallel programs remained open until very recently. Specifically, Boyle, Chung and Pass in their upcoming TCC 2016 paper (see their recently updated eprint version) have recently shown how to garbled PRAM program with poly-logarithmic (parallel) overhead assuming non-black-box use of identity-based encryption. The question whether such a strong assumption and non-black-box use of such a strong assumption are needed. In this paper, we resolve this important open question and show how to garble parallel programs, with only black-box use one one-way functions and with only poly-log overhead in the (parallel) running time. Our result works for any number of parallel processors.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
PRAMGarbled RAMBlack-Box CryptographyOne-Way FunctionsSecure Computation
Contact author(s)
stevelu8 @ gmail com
History
2015-11-03: received
Short URL
https://ia.cr/2015/1068
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1068,
      author = {Steve Lu and Rafail Ostrovsky},
      title = {Black-Box Parallel Garbled RAM},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1068},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1068}},
      url = {https://eprint.iacr.org/2015/1068}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.