Paper 2014/766

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.