Take the 2-minute tour ×
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.

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

share|improve this question

migrated from stackoverflow.com Nov 5 '12 at 13:22

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

add comment

1 Answer 1

up vote 3 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: crypto.stackexchange.com/q/14436/7760. –  Kartik Feb 11 at 11:55
add comment

Your Answer

 
discard

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.