Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 :)

share|improve this question
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) – D.W. Jun 5 '14 at 6:45
up vote 8 down vote accepted

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.

share|improve this answer
Welcome to the site. Glad to have you here! – mikeazo Jun 12 '14 at 13:48
Thank you! I hope to be of use. – Chris Peikert Jun 12 '14 at 23:20
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? – kekx Jun 16 '14 at 10:49
See the last sentence of my answer -- the circuit is not revealed, but encoded by the multi linear map. – Chris Peikert Jun 16 '14 at 11:13
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. – kekx Jun 16 '14 at 14:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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