Rafail Ostrovsky - Publications

Black-Box Parallel Garbled RAM

Steve Lu, Rafail Ostrovsky


In 1982, Yao introduced a technique of "circuit garbling" that became a central building block in cryptography. The question of garbing general random-access memory (RAM) programs was introduced by lu and Ostrovsky in 2013. The most recent results of Garg,Lu, and Ostrovsky (FOCS 2015) achieve a garbled RAM with black-box use of any oneway functions and poly-log overhead of data and program garbling in all the relevant parameters, including program run-time. The advantage of garbled RAM 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 TCC 2016-A [4] have shown how to garble PrAM programs with poly-logarithmic (parallel )overhead assuming non-black use identity-based encryption (IBE). The question of whether the IBE assumption, and in particular, the non black-box use of such a strong assumption is needed. In this paper, we resolve this question and show how to garble paralel programs, with black-box use of only one-way functions and with only poly-log overhead in the (parallel) running time. Out result works for any number of paralle processors.

comment: CRYPTO (2) 2017: 66-92

Fetch PDF file of the paper

Back to Publications List