Paper 2014/942

Public-Coin Differing-Inputs Obfuscation and Its Applications

Yuval Ishai, Omkant Pandey, and Amit Sahai

Abstract

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, and related primitives. Roughly speaking, a diO scheme ensures that the obfuscations of two efficiently generated programs are indistinguishable not only if the two programs are equivalent, but also if it is hard to find an input on which their outputs differ. The above ``indistinguishability'' and ``hardness'' conditions should hold even in the presence of an auxiliary input that is generated together with the programs. The recent works of Boyle and Pass (ePrint 2013) and Garg et al. (Crypto 2014) 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 {\em public-coin} diO. A public-coin diO restricts the original definition of diO by requiring the auxiliary input to be a public random string which is given as input to all relevant algorithms. In contrast to standard diO, we argue that 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 {\em succinct} obfuscation and functional encryption schemes for Turing Machines, where the size of the obfuscated code or keys is essentially independent of the running time and space.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Program ObfuscationDiffering Inputs ObfuscationFunctional EncryptionObfuscation for Turing Machines
Contact author(s)
omkant @ gmail com
History
2015-01-13: last of 2 revisions
2014-11-18: received
See all versions
Short URL
https://ia.cr/2014/942
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/942,
      author = {Yuval Ishai and Omkant Pandey and Amit Sahai},
      title = {Public-Coin Differing-Inputs Obfuscation and Its Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/942},
      year = {2014},
      url = {https://eprint.iacr.org/2014/942}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.