4

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?

Improve this question

1 Answer 1

Reset to default
2

Your DeObf() can extract a non-trivial property of C1 that C2 does not share, so it acts as a "distinguisher". This contradicts the existence of the indistinguishability obfuscator, even if the output of DeObf is only an approximate deobfuscation.

Running time cannot be used to break an indistinguishability circuit obfuscator. An indistinguishability obfuscator only has to work on circuits of comparable size. It is allowed to produce a circuit Obf(C2) noticeably different from Obf(C1) if C2 is very much larger than C1.

Less is known formally about obfuscation of Turing machines (and real programs), although there are some results. The latest constructions are proven secure only against "generic" attacks. Such proofs have previously been known to be contradicted by non-generic attacks.

Improve this answer
6
  • Thank you @Steve Michell, I am trying to understand what you said. Do you want to say that: let C2=DeObf(Obf(C1)) and suppose that C2 has a non-trivial property p then the existence of DeObf implies that Obf leaks a non-trivial property of C1: "there exists a circuit (i.e. program) C2 having property p and C2 is mostly equivalent to C1"?
    – Ta Thanh Dinh
    Jan 11, 2014 at 8:33
  • I still do not understand what you mean in this phrase "Running time cannot be used to break an indistinguishability circuit obfuscator. An indistinguishability obfuscator only has to work on circuits of comparable size."
    – Ta Thanh Dinh
    Jan 11, 2014 at 11:16
  • I'm simply applying the definition of indistinguishability (Garg et al, Definition 1) to your example. You propose that if C1 has property P and C2 does not have property P, then based on your deobfuscator you can write some P-distinguisher D so that D(DeObf(Obf(C1))) = true and D(DeObf(Obf(C2))) = false with some noticeable probability. That's precisely what Obf() prevents, according to the definition.
    – Steve Mitchell
    Jan 13, 2014 at 23:14
  • Your original question contains a clever suggestion to use complexity (running time = circuit depth) as a property for distinguishing obfuscated sorting programs (e.g., QuickSort vs BubbleSort.) But in a mild example, the obfuscator will simply slow down the faster program. For an extreme example, imagine that the sorting program runs a long loop before returning. The corresponding circuit will be very deep, and the obfuscator will refuse to process it. In Garg et al's Definition 1, the obfuscator takes a size parameter Obf(\lambda, C).
    – Steve Mitchell
    Jan 13, 2014 at 23:44
  • Thank again @Steve Mitchell but I am still not understand what you said in this phrase "I'm simply applying the definition of indistinguishability...". As far as I understand, you mean that your exemplified property p is the input/output semantics of the program?, if it is the case then p is just a trivial property (i.e. exists in all programs of the same I/O semantics) and such a property is preserved by all obfuscation techniques.
    – Ta Thanh Dinh
    Jan 14, 2014 at 14:27

Your Answer

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

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