Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

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

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:

share|improve this question

migrated from Nov 5 '12 at 13:22

This question came from our site for professional and enthusiast programmers.

up vote 4 down vote accepted

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

share|improve this answer
Thank you much! – rostamn739 Nov 5 '12 at 10:03
Follow up question: – Kartik Feb 11 '14 at 11:55

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.