Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / garbling schemes, succinct randomized encodings, adaptive security, functional encryption

Date: received 17 Aug 2018, last revised 17 Aug 2018

Contact author: alexjl at mit edu

Available format(s): PDF | BibTeX Citation

Version: 20180820:181849 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]