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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2012/601}},
      url = {https://eprint.iacr.org/2012/601}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.