2
$\begingroup$

Might it be possible that reversible combinatorial circuits (or some emulating software) are going to be used to get the input of the white box?

I mean if I have constructed a proper reversible circuit then (in theory) I can obtain the input of whatever output I get. Am I missing the point?

Here is the relevant WP link for those interested: http://en.wikipedia.org/wiki/Toffoli_gate

$\endgroup$
0

1 Answer 1

4
$\begingroup$

Such a reversible circuit would have many additional output lanes. Since there are too many different values those can have(exponential in the number of extra lanes) you can't guess a complete output of such a circuit. Without a complete output of the circuit you can't reverse it. So your approach doesn't work.

If you could construct a reversible circuit with few additional output lanes, that'd break a hash-function. But there is no simple way construct such a circuit given a normal circuit.

The Toffoli gate is universal; this means that for any boolean function f(x1, x2, ..., xm), there is a circuit consisting of Toffoli gates which takes x1, x2, ..., xm and some extra bits set to 0 or 1 and outputs x1, x2, ..., xm, f(x1, x2, ..., xm), and some extra bits (called garbage). Essentially, this means that one can use Toffoli gates to build systems that will perform any desired boolean function computation in a reversible manner.

Quoted from Wikipedia: Toffoli gate

$\endgroup$
1

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.