Why can't hashes be reversed with toffoli gates? This is a follow up question to this question: Crack cryptographic hash functions using Toffoli gates?.

Suppose there is a hash function $$H(x)=y,$$ where $x$ is the input of the function and $y$ is the hash of $x$. Now, suppose we have made an emulating software that emulates $H(x)$ using Toffoli gates. This new function can be denoted by $$T(x)=(y,z),$$ where $z$ is the garbage. Now toffoli gates are reversible, so we can make a function $$T^{-1}(y,z)=x.$$ Now the problem is that we do not know $z$, because it was lost during the calculation of $H(x)$.

Now we can choose any random (but valid) garbage $z'$ and calculate $$T^{-1}(y,z')=x'.$$ Now by definition of $T^{-1}$, we have $T(x')=(y,z')$; and so $$H(x')=y.$$ So we have found a collision (if not the original value).



I know very less about cryptography, and I know something must be wrong in the above but I cannot find out what is wrong. So, please tell me what is wrong. I do not have the neccesary information and software to test this procedure.



Example

This is a very simple example. More complicated examples can be difficult to calculate by hand.

Suppose $x\in(0,1)$ and $H(x)=x\land1$. Now we will try to reverse the output $H(x)=0$. Now let's denote the toffoli gate by $G(x,y,z)$. The function $H(x)=x\land 1$ can be converted into $$T(x)=(y,z) \rightarrow G(x,1,0)=(y,z_1,z_2).$$ Reverse of this is $$T^{-1}(y,z)=(x) \rightarrow G^{-1}(y,z_1,z_2)=(x,1,0).$$ We have $y=1$. Let's choose $z'=(1,0)$. Now calculate $$T^{-1}(1,(1,0))=1 \Leftarrow G^{-1}(1,1,0) = (1,1,1).$$ So, we have $H(1)=1$. This is the answer! (Because $1\land1=1$)
The question errs precisely at the point when it writes: $$\text{and so }H(x')=y.$$

Problem is: that holds for $x'$ matching some garbage $z'$, including $z'=z$, and perhaps other garbage $z'$, but we do not know which garbage (or $z$ unless we know $x$), and I see no reason that it holds for $x'$ obtained from any garbage $z'$ except for trivial $H$; and in the question $z'$ is random.

The only constructive process (as opposed to search) that I can think of to exhibit garbage $z'$ such that $H(x')=y$ is clause resolution or some improvement of that, well known to be exponential, as well as its sequential alternative.



Or otherwise said, my understanding of Toffoli-gate equivalent circuits (still limited, but improved in the process of making the present answer) is that they really are of the form $T(x,z)\mapsto(y,z)$ where it is easy to deduce $z$ from $x$ such that $H(x)=y$ holds, but not to deduce $z$ from $y$ such that $H(x)=y$ holds. Or, if we insist on the $T(x)\mapsto(y,z)$ notation, that is use $z$ built from inputs taken from $x$, we need $x$ to exhibit $z$.