Cryptology ePrint Archive: Report 2015/307

Black-Box Garbled RAM

Sanjam Garg and Steve Lu and Rafail Ostrovsky

Abstract: Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao's garbled circuit construction, except that known realizations of Garbled RAM make non-black-box use of the underlying cryptographic primitives.

In this paper we remove this limitation and provide the first black-box construction of Garbled RAM with polylogarithmic overhead. Our scheme allows for garbling multiple RAM programs being executed on a persistent database and its security is based only on the existence of one-way functions. We also obtain the first secure RAM computation protocol that is both constant round and makes only black-box use of one-way functions in the OT-hybrid model.

Category / Keywords: foundations / Garbled RAM, Secure Computation, Black-box Cryptography

Original Publication (with minor differences): FOCS 2015

Date: received 2 Apr 2015, last revised 15 Jul 2015

Contact author: stevelu8 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150715:193242 (All versions of this report)

Short URL: ia.cr/2015/307

Discussion forum: Show discussion | Start new discussion