Paper 2015/307

Black-Box Garbled RAM

Sanjam Garg, Steve Lu, and Rafail Ostrovsky


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.

Available format(s)
Publication info
Published elsewhere. Minor revision. FOCS 2015
Garbled RAMSecure ComputationBlack-box Cryptography
Contact author(s)
stevelu8 @ gmail com
2015-07-15: revised
2015-04-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sanjam Garg and Steve Lu and Rafail Ostrovsky},
      title = {Black-Box Garbled {RAM}},
      howpublished = {Cryptology ePrint Archive, Paper 2015/307},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.