Latest update

Quantum attack on classical hash functions

2018-10-11 19:37:31

Consider a classical hash function that gives $x\rightarrow c = H(x)$, where $c$ is a commitment. I know how to program $H$ on a classical computer so I write the quantum circuit, $U$, for it.

$\vert x\rangle\otimes\vert y\rangle\xrightarrow{U}\vert x\rangle\otimes\vert H(x)\oplus y\rangle$.

I apply a Hadamard on the input state $\vert 0 \rangle$ to get $\sum_{i}\vert x_i\rangle$ - all possible input strings. Next, I build the inverse for the quantum circuit and so, for any given $c_0 = H(x_0)$

$\sum_{i}\vert x_i\rangle\otimes \vert c_0\rangle \xrightarrow{U^{\dagger}} \sum_{i}\vert x_i\rangle \otimes \vert i\rangle$, where $\vert i \rangle$ is something we can't control.

However, if I measure the second register with $\vert 0 \rangle\langle 0 \vert$, this gives me, in the first register $\sum_{i : H(x_i) = c_0} x_i$.

What am I doing wrong here? This seems to suggest that hash functions can be easily broken by a quantum computer although the literature says that th