### Succinct Garbling Schemes and Applications

Huijia Lin and Rafael Pass

##### Abstract

Assuming the existence of iO for P/poly and one-way functions, we show how to succinctly garble bounded-space computations (BSC) M: the size of the garbled program (as well as the time needed to generate the garbling) only depends on the size and space (including the input and output) complexity of M, but not its running time. The key conceptual insight behind this construction is a method for using iO to "compress" a computation that can be performed piecemeal, without revealing anything about it. As corollaries of our succinct garbling scheme, we demonstrate the following: -functional encryption for BSC from iO for P/poly and one-way functions; -reusable succinct garbling schemes for BSC from iO for P/poly and one-way functions; - succinct iO for BSC from sub-exponentially-secure iO for P/poly and sub-exponentially secure one-way functions; - (PerfectNIZK) SNARGS for bounded space and witness NP from sub-exponentially-secure iO for P/poly and sub-exponentially-secure one-way functions. Previously such primitives were only know to exists based on “knowledge-based” assumptions (such as SNARKs and/or differing-input obfuscation). We finally demonstrate the first (non-succinct) iO for RAM programs with bounded input and output lengths, that has poly-logarithmic overhead, based on the existence of sub-exponentially-secure iO for P/poly and sub-exponentially-secure one-way functions.

Available format(s)
Publication info
Preprint. MINOR revision.
Keywords
Succinct Garbling SchemeIO for RAMBounded Space Computation
Contact author(s)
huijial @ gmail com
History
Short URL
https://ia.cr/2014/766

CC BY

BibTeX

@misc{cryptoeprint:2014/766,
author = {Huijia Lin and Rafael Pass},
title = {Succinct Garbling Schemes and Applications},
howpublished = {Cryptology ePrint Archive, Paper 2014/766},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/766}},
url = {https://eprint.iacr.org/2014/766}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.