Succinct Garbling Schemes from Functional Encryption Through a Local Simulation Paradigm

Prabhanjan Ananth, Alex Lombardi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 16th International Conference, TCC 2018, Proceedings
EditorsAmos Beimel, Stefan Dziembowski
PublisherSpringer Science and Business Media Deutschland GmbH
Pages455-472
Number of pages18
ISBN (Print)9783030038090
DOIs
StatePublished - 2018
Externally publishedYes
Event16th International Conference on Theory of Cryptography, TCC 2018 - Panaji, India
Duration: Nov 11 2018Nov 14 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11240 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Theory of Cryptography, TCC 2018
Country/TerritoryIndia
CityPanaji
Period11/11/1811/14/18

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Succinct Garbling Schemes from Functional Encryption Through a Local Simulation Paradigm'. Together they form a unique fingerprint.

Cite this