Paper 2013/650

On Extractability (a.k.a. Differing-Inputs) Obfuscation

Elette Boyle, Kai-Min Chung, and Rafael Pass

Abstract

We initiate the study of {\em extractability obfuscation}, a notion first suggested by Barak et al. (JACM 2012): An extractability obfuscator eO for a class of algorithms M guarantees that if an efficient attacker A can distinguish between obfuscations eO(M_1), eO(M_2) of two algorithms M_1,M_2 \in M, then A can efficiently recover (given M_1 and M_2) an input on which M_1 and M_2 provide different outputs. - We rely on the recent candidate virtual black-box obfuscation constructions to provide candidate constructions of extractability obfuscators for NC^1; next, following the blueprint of Garg et~al. (FOCS 2013), we show how to bootstrap the obfuscator for NC^1 to an obfuscator for all non-uniform polynomial-time Turing machines. In contrast to the construction of Garg et al., which relies on indistinguishability obfuscation for NC^1, our construction enables succinctly obfuscating non-uniform {\em Turing machines} (as opposed to circuits), without turning running-time into description size. - We introduce a new notion of {\em functional witness encryption}, which enables encrypting a message m with respect to an instance x, language L, and function f, such that anyone (and only those) who holds a witness w for x\in L can compute f(m,w) on the message and particular known witness. We show that functional witness encryption is, in fact, equivalent to extractability obfuscation. - We demonstrate other applications of extractability extraction, including the first construction of fully (adaptive-message) indistinguishability-secure functional encryption for an unbounded number of key queries and unbounded message spaces. - We finally relate indistinguishability obfuscation and extractability obfuscation and show special cases when indistinguishability obfuscation can be turned into extractability obfuscation.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in TCC 2014
Keywords
ObfuscationWitness EncryptionFunctional EncryptionExtractability
Contact author(s)
eboyle @ alum mit edu
History
2014-04-16: last of 3 revisions
2013-10-15: received
See all versions
Short URL
https://ia.cr/2013/650
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/650,
      author = {Elette Boyle and Kai-Min Chung and Rafael Pass},
      title = {On Extractability (a.k.a. Differing-Inputs) Obfuscation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/650},
      year = {2013},
      url = {https://eprint.iacr.org/2013/650}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.