We shall say that an obfuscator $\mathcal{O}$ is a reversible black box obfuscator if for each reversible program $P$ the obfuscated program $\mathcal{O}(P)$ is still reversible but does not reveal any more information than an oracle that computes $x\mapsto P(x)$ along with an oracle that computes $x\mapsto P^{-1}(x)$. It is well-known that black box obfuscators do not exist. Do reversible black box obfuscators exist?


1 Answer 1


By "reversible program" I assume you mean an injective function.

The answer to your question is no, there is no black-box obfuscator for the set of injective functions.

The idea is to make an unobfuscatable function invertible using the Feistel trick. More formally, if $g: \{0,1\}^n \to \{0,1\}^n$ define $Feistel_g : \{0,1\}^{2n} \to \{0,1\}^{2n}$ as

$$Feistel_g(x,y) = (x, g(x) \oplus y).$$

$Feistel_g$ is invertible regardless of $g$ (and a similar thing works when the input/output lengths of $g$ are different).

Let $\mathcal{G}$ be the unobfuscatable function family from the Barak et al paper. Then define

$$Feistel_\mathcal{G} = \{ Feistel_g \mid g \in \mathcal{G} \}$$

Then this family consists of only invertible functions. Furthermore it is black-box unobfuscatable because black-box access to $g$ can be simulated given black-box access to $Feistel_g$ (and vice-versa). And oracle access to $(Feistel_g)^{-1}$ is redundant since $Feistel_g$ is its own inverse.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.