Elette Boyle

Extractability Obfuscation


We initiate the study of 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 Turing machines (as opposed to circuits), without 
turning running-time into description size.

- We introduce a new notion of 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 

- We finally relate indistinguishability obfuscation and extractability 
obfuscation and show special cases when indistinguishability obfuscation 
can be turned into extractability obfuscation.

Joint work with Kai-Min Chung and Rafael Pass.