# Performing DFS search with garbled boolean circuit

Given $G=(V,E)$

How can i implement a DFS search in the Boolean circuit? ( The output should be to assign each node it's DFS value from a root node)

I assume the complexity should be exponential, because each move we don't know the next node to be it's consequent node).

But is there any justification to that? Can I do it better?

The above question is algorithmic, Because it's a preliminary stage to make the circuit obliviously...

Thanks.

• For any program running in T steps using N memory, you can compile it to an oblivious version with ~O(T\log N) steps. An oblivious version can then be compiled to a circuit in a straightforward manner. No guarantee in terms of concrete cost. Jan 12 '18 at 2:11