# Are hash functions really quantum resistant for commitment schemes?

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.

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!).
• Very nice answer. Can one state that the difficulty in inverting the quantum SHA2 is equivalent to figuring out the ancilla output states of the quantum equivalent of H such that the input ancilla states are all $\vert 0\rangle$? And on a related note, do you have any comments on the line of research pursued in the paper I linked in the question? It appears to claim that classical commitment schemes do not hold in the quantum regime but your argument suggests that this is not an issue. – user1936752 Oct 10 '18 at 21:54