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