Paper 2015/307 Original: eprint.iacr.org/2015/307 ↗
Black-Box Garbled RAM
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2015-07-15: last updated
- 2015-04-06: published
- Short URL
- https://ia.cr/2015/307
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2015/307,
author = {Sanjam Garg and Steve Lu and Rafail Ostrovsky},
title = {Black-Box Garbled RAM},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/307},
year = {2015},
url = {https://eprint.iacr.org/2015/307}
}