2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user1936752 Oct 10 '18 at 21:54
  • 1
    $\begingroup$ @user1936752, on your first question: yup, that sounds right to me. On the paper: the paper is considering something orthogonal to the issue I address in my answer. The paper talks about quantum attacks on commitment schemes, something that my argument doesn't address. $\endgroup$ – D.W. Oct 11 '18 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.