Are hash functions really quantum resistant for commitment schemes?

Question

It is commonly stated that hash functions remain secure in a post quantum world, the justification being that a quantum computer only has the advantage of Grover's search to give it a quadratic speedup.

However, there is active research into, for example, commitments such as https://eprint.iacr.org/2015/361.pdf. These state that in a quantum setting (whatever that means), the old way of doing commitments by requiring collision resistance doesn't work.

My understanding (possibly wrong) is that one cannot implement a hash function with quantum operators and gates because the quantum operators are unitary and therefore the hash function becomes invertible. The classical hash function uses compression to lose information and is hence, non-invertible. Is there then a possibility that if we attempted a quantum implementation of SHA-2, that would end up showing us how to break it?

Consider $x \rightarrow y = H(x)$. If I have an implementation of $H$ with quantum gates, I could take any $y$, put the remaining registers into whatever state I want (corresponding to the lost information) and then invert to obtain a valid $x$. My only assumption here is that I implemented the quantum $H$ but I can't see why this is forbidden, or even difficult.

Answer 1

No. I can see how that sounds like it could work, but it doesn't actually work. You're missing an important detail about how we implement classical functions on a quantum computer. The usual way to implement non-reversible functions with reversible logic is to use ancilla bits (i.e., constant inputs, and junk outputs that are discarded).

For instance, suppose you want to implement the function $f(x,y) = x \land y$ (it computes the boolean AND of its two inputs). You can make this invertible by instead implementing $g(x,y,z) = ((x \land y) \oplus z, x, y)$ (here $\oplus$ denotes XOR). Here $g$ is called a Toffoli gate. Note that $g$ is invertible, even though $f$ is not. Moreover, we can compute $f$ by noting that $g(x,y,0) = (f(x,y,0),x,y)$, so if you want to compute $f$ in a reversible way, you feed in $x$, $y$, and a constant $0$ to $g$, then discard all but the first bit of output. Just because you can invert $g$ doesn't mean you can invert $f$. First, given only $f(x,y)$, we don't know what value to place into the other output bits of $g$. Second, if we made random guesses at those outputs and then inverted $g$, that won't necessarily give us an inverse of $f$ (try it!).

The same is true for SHA2. We know how to implement SHA2 on a quantum computer. It uses ancilla bits. Those ancilla bits prevent you from inverting SHA2 by trying to reverse the quantum computation.