I have some superficial thinking about the indistinguishability obfuscation, these come from this question of @perror and the answer of @mikeazo herein about a construction of the indistinguishability obfuscator given in this paper.
IMHO, this obfuscator is really a breakthrough because it says that, theoretically, we can write obfuscated programs so that the properties being extracted from them are always trivial. To get it more clearly, we consider the set of all programs:
Progs = { P1,P2,...,Pn,... }
of the same semantics as a program P, then the properties can be extracted from an obfuscated version Obf(P) of P (obviously Obf(P) is in Progs) are also exists in programs in Progs, namely we cannot distinguish Obf(P) from any program in Progs.
For example, lets P be a program implementing a sorting algorithm (e.g. bublesort) then Progs consists of all programs implementing all sorting algorithms (e.g. quicksort, insertion sort, etc). Then the interesting is we cannot classify Obf(P) into any existed sorting algorithms, it mixes all possible algorithms: for some inputs, it behave as bublesort, for other inputs it behave as quicksort, etc. Because if we can classify into some existed algorithms, then that means we can extract a non-trivial information (e.g. the complexity of the algorithm) from Obf(P).
The problem is a such obfuscator transforms always a program into a semantics equivalent program. But if a reverser, using some deobfuscator DeObf, can approximate Obf(P) with a "human understandable" program:
P' = DeObf(Obf(P))
namely P' and Obf(P) are not semantically equivalent, but they are "mostly" equivalent: in the most case, P' returns the same output as Obf(P) given the same input.
A very naive idea comes to me is to "instrument" the code of Obf(P) (e.g. insert some deobfuscating procedures into Obf(P), they execute with Obf(P) but not change too much the semantics of Obf(P)), we may extract some non-trivial properties.
So my question is: Does the existence of DeObf contradict the existence of the indistinguishability obfuscator Obf?
Could anyone gives me some suggestions?