Cryptology ePrint Archive: Report 2015/388

Succinct Garbled RAM

Ran Canetti and Justin Holmgren

Abstract: We construct the first fully succinct garbling scheme for RAM programs, assuming the existence of indistinguishability obfuscation for circuits and one-way functions. That is, the size, space requirements, and runtime of the garbled program are the same as those of the input program, up to poly-logarithmic factors and a polynomial in the security parameter. The scheme can be used to construct indistinguishability obfuscators for RAM programs with comparable efficiency, at the price of requiring sub-exponential security of the underlying primitives.

In particular, this opens the door to obfuscated computations that are {\em sublinear} in the length of their inputs.

The scheme builds on the recent schemes of Koppula-Lewko-Waters and Canetti-Holmgren-Jain-Vaikuntanathan [STOC 15]. A key technical challenge here is how to combine the fixed-prefix technique of KLW, which was developed for deterministic programs, with randomized Oblivious RAM techniques. To overcome that, we develop a method for arguing about the indistinguishability of two obfuscated randomized programs that use correlated randomness. Along the way, we also define and construct garbling schemes that offer only partial protection. These may be of independent interest.

Category / Keywords: public-key cryptography / indistinguishability obfuscation, RAM programs, Oblivious RAM

Date: received 25 Apr 2015, last revised 30 Sep 2015

Contact author: holmgren at mit edu

Available format(s): PDF | BibTeX Citation

Version: 20150930:222402 (All versions of this report)

Short URL: ia.cr/2015/388

Discussion forum: Show discussion | Start new discussion