Paper 2012/601
How to Garble RAM Programs
Steve Lu and Rafail Ostrovsky
Abstract
Assuming solely the existence of one-way functions, we show how to construct Garbled RAM Programs (GRAM) where its size only depends on fixed polynomial in the security parameter times the program running time. We stress that we avoid converting the RAM programs into circuits. As an example, our techniques implies the first garbled binary search program (searching over sorted encrypted data stored in a cloud) which is poly-logarithmic in the data size instead of linear. Our result requires the existence of one-way function and enjoys the same non-interactive properties as Yao's original garbled circuits.
Metadata
- Available format(s)
-
PDF
PS
- Publication info
- Published elsewhere. To Appear in EUROCRYPT 2013
- Keywords
- Secure ComputationOblivious RAMGarbled Circuits
- Contact author(s)
- steve @ stealthsoftwareinc com
- History
- 2013-03-13: last of 8 revisions
- 2012-10-25: received
- See all versions
- Short URL
- https://ia.cr/2012/601
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2012/601,
author = {Steve Lu and Rafail Ostrovsky},
title = {How to Garble {RAM} Programs},
howpublished = {Cryptology {ePrint} Archive, Paper 2012/601},
year = {2012},
url = {https://eprint.iacr.org/2012/601}
}
