2014 | OriginalPaper | Chapter
On Extractability Obfuscation
Authors : Elette Boyle, Kai-Min Chung, Rafael Pass
Published in: Theory of Cryptography
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We initiate the study of
extractability obfuscation
, a notion first suggested by Barak
et al.
(JACM 2012): An extractability obfuscator
$e{\mathcal{O}}$
for a class of algorithms
$\mathcal{M}$
guarantees that if an efficient attacker
$\mathcal{A}$
can distinguish between obfuscations
$e{\mathcal O}(M_1), e{\mathcal O}(M_2)$
of two algorithms
$M_1,M_2 \in{\mathcal{M}}$
, then
$\mathcal{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
∈
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.