Succinct Garbled RAM

Ran Canetti; Justin Holmgren

Paper 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 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.

Note: Added acknowledgement and fixed typo

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Major revision. ITCS 2016
DOI: 10.1145/2840728.2840765
Keywords: indistinguishability obfuscation RAM programs Oblivious RAM
Contact author(s): justin holmgren @ gmail com
History: 2019-05-17: last of 3 revisions; 2015-04-29: received; See all versions
Short URL: https://ia.cr/2015/388
License: CC BY

BibTeX

@misc{cryptoeprint:2015/388,
      author = {Ran Canetti and Justin Holmgren},
      title = {Succinct Garbled {RAM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/388},
      year = {2015},
      doi = {10.1145/2840728.2840765},
      url = {https://eprint.iacr.org/2015/388}
}