Summer 2015

Public-Coin Differing-Inputs Obfuscation and its Applications

Thursday, June 11th, 2015 9:30 am9:55 am

Add to Calendar


Calvin Lab Auditorium

Differing inputs obfuscation (diO) is a strengthening of indistinguishability obfuscation (iO) that has recently found applications to improving the efficiency and generality of obfuscation, functional encryption, non-black-box simulation, and several other related primitives. These applications require the “security” of diO to hold even in the presence of an auxiliary input that is generated together with the programs. However, recent negative results cast serious doubt on the plausibility of general-purpose diO with respect to general auxiliary inputs. This leaves open the existence of a variant of diO that is plausible, simple, and useful for applications.

We suggest such a diO variant that we call *public-coin* diO. A public-coin diO restricts the original definition of diO by requiring the auxiliary input to be a public, trapdoor-free, random string which is given as input to all relevant algorithms. In contrast to standard diO, it remains very plausible that current candidate constructions of iO for circuits satisfy the public-coin diO requirement. 

We demonstrate the usefulness of the new notion by showing that several applications of diO can be obtained by relying on the public-coin variant instead. These include constructions of succinct obfuscation and functional encryption schemes for Turing Machines as well as obfuscation-based non-black-box simulation for (concurrent) zero-knowledge.

Joint work with Yuval Ishai and Amit Sahai.