Paper 2018/759

Succinct Garbling Schemes from Functional Encryption through a Local Simulation Paradigm

Prabhanjan Ananth and Alex Lombardi

Abstract

We study a simulation paradigm, referred to as local simulation, in garbling schemes. This paradigm captures simulation proof strategies in which the simulator consists of many local simulators that generate different blocks of the garbled circuit. A useful property of such a simulation strategy is that only a few of these local simulators depend on the input, whereas the rest of the local simulators only depend on the circuit. We formalize this notion by defining locally simulatable garbling schemes. By suitably realizing this notion, we give a new construction of succinct garbling schemes for Turing machines assuming the polynomial hardness of compact functional encryption and standard assumptions (such as either CDH or LWE). Prior constructions of succinct garbling schemes either assumed sub-exponential hardness of compact functional encryption or were designed only for small-space Turing machines. We also show that a variant of locally simulatable garbling schemes can be used to generically obtain adaptively secure garbling schemes for circuits. All prior constructions of adaptively secure garbling that use somewhere equivocal encryption can be seen as instantiations of our construction.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
garbling schemessuccinct randomized encodingsadaptive securityfunctional encryption
Contact author(s)
alexjl @ mit edu
History
2018-08-20: received
Short URL
https://ia.cr/2018/759
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/759,
      author = {Prabhanjan Ananth and Alex Lombardi},
      title = {Succinct Garbling Schemes from Functional Encryption through a Local Simulation Paradigm},
      howpublished = {Cryptology ePrint Archive, Paper 2018/759},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/759}},
      url = {https://eprint.iacr.org/2018/759}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.