5
$\begingroup$

I am currently working on an implementation of the candidate construction for an indistinguishability obfuscator that was recently proposed by Garg et al. The relevant paper can be found here. Specifically I am only implementing the construction for circuits in NC1, because the construction for polynomial-sized circuits requires homomorphic-encryption.

In the construction of the indistinguishability obfuscator, they transform a universal circuit into a branching program and fix parts of its input to obtain the obfuscation of the original circuit. Since universal circuits can be quite big and tedious to generate, I am wondering, why it's even necessary to use them. In how far is a universal circuit with partially fixed inputs different from the original circuit? Would it not be possible to simply transform the original circuit into a branching program and apply the whole obfuscation process to it?

The proof of security in the paper is not trivial to me, so it's not clear for me, in how far the security relies on the usage of the universal circuit. I'd be thankful for any enlightenment on the issue :)

$\endgroup$
1
  • 1
    $\begingroup$ I don't know. Maybe the security proof requires use of the universal circuit? (e.g., to ensure the branching program will have the same structure regardless of what the original circuit is, or something) $\endgroup$
    – D.W.
    Jun 5, 2014 at 6:45

1 Answer 1

9
$\begingroup$

As @D.W. guessed, the branching program for a circuit essentially reveals the original circuit. It's not clear what you mean by "apply the whole obfuscation process to the circuit-revealing branching program," but the prospects for that do not seem good: evaluating the branching program is highly sequential (polynomial depth), and you would need to obfuscate that procedure. In all, you've reduced the goal of "obfuscate a log-depth circuit" to "obfuscate a poly-depth circuit" – that's negative progress!

By contrast, the universal circuit has a fixed branching program, so it obviously reveals nothing about the circuit to be obfuscated (except an upper bound on its size). Also, the UC's input (the circuit to be obfuscated) is "concealed" by the multilinear map.

$\endgroup$
8
  • 3
    $\begingroup$ Welcome to the site. Glad to have you here! $\endgroup$
    – mikeazo
    Jun 12, 2014 at 13:48
  • $\begingroup$ While it is clear, that the branching program for the universal circuit doesn't reveal anything about the original circuit, the construction uses the branching program for the universal circuit and fixes the parts of its inputs that correspond to the original circuits binary representation. I am still struggling to understand in how far the branching program for the original circuit is any different from the branching program for the universal circuit with partially fixed inputs. Aren't they essentially the same? $\endgroup$
    – kekx
    Jun 16, 2014 at 10:49
  • $\begingroup$ See the last sentence of my answer -- the circuit is not revealed, but encoded by the multi linear map. $\endgroup$ Jun 16, 2014 at 11:13
  • $\begingroup$ Yeah, but if I encode the branching program of the original circuit with the multi linear map, does this not result in the same security? As I said, I don't fully understand the proof of security in the paper, but it seems to me that it does not rely on the usage of the universal circuit, but only on the fact that the resulting matrices can only be multiplied together in the correct order. $\endgroup$
    – kekx
    Jun 16, 2014 at 14:39
  • $\begingroup$ I don't think it does. The branching program of the original circuit includes, in particular, which input bit to read to select a matrix from each pair of matrices in the BP. This correspondence reveals a lot (maybe everything) about the original circuit. $\endgroup$ Jun 16, 2014 at 15:48

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.