- 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.
Category / Keywords: public-key cryptography / Obfuscation, Witness Encryption, Functional Encryption, Extractability Original Publication (with minor differences): IACR-TCC-2014 Date: received 9 Oct 2013, last revised 16 Apr 2014 Contact author: eboyle at alum mit edu Available format(s): PDF | BibTeX Citation Version: 20140416:172215 (All versions of this report) Short URL: ia.cr/2013/650 Discussion forum: Show discussion | Start new discussion