Succinct Garbling Schemes and Applications

Huijia Lin; Rafael Pass

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.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: Succinct Garbling Scheme IO for RAM Bounded Space Computation
Contact author(s): huijial @ gmail com
History: 2014-09-30: received
Short URL: https://ia.cr/2014/766
License: 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}
}