Cryptology ePrint Archive: Report 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.

Category / Keywords: Secure Computation, Oblivious RAM, Garbled Circuits

Publication Info: To Appear in EUROCRYPT 2013

Date: received 24 Oct 2012, last revised 13 Mar 2013

Contact author: steve at stealthsoftwareinc com

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20130313:162324 (All versions of this report)

Discussion forum: Show discussion | Start new discussion