Quantum attack on hash functions

Question

The line of questioning is inspired by the pick one trick in Section 4 of the PDF version of the paper Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding (Ambainis et al., 2014). Slides available here. I don't fully follow the argument there so maybe I missed something important but here is my interpretation of their trick.

Consider a classical hash function $x \rightarrow H(x)$ that is collision resistant i.e. it is computationally hard to find $H(x) = H(x') \land x\neq x'$. We wish to encode a commitment of a message using this hash function. That is, I take some message $m$ and concatenate some randomness $u$ at the end such that I generate a commitment $c = H(m\Vert u)$. When asked to prove my commitment, I cannot find a different pair $(m',u')$ such that $c = H(m'\Vert u')$ because of the collision-free nature of hashes. My only choice is to open the commitment to $(m,u)$.

Now, we attack this protocol with a quantum circuit of the hash function.

1. Take a superposition over all possible inputs $x_i$ and query the hash function with this state to obtain the state $\vert\psi\rangle = \sum_{i}\vert x_i\rangle\vert H(x_i)\rangle$.

2. Measure the second register to obtain a random commitment. The measurement randomly picks $c = H(x_i)$ for some $i$. The first register then has $\vert\phi\rangle = \sum_j \vert x_j\rangle$ such that $\forall j, c = H(x_j)$.

3. I'd like to open the commitment to some $m'$ that is given to me by the opponent. Use Grover's search on the first register to find a $x_{\text{sol}}$ from the state $\vert\phi\rangle = \sum_j\vert x_j\rangle$ that satisfies some special property. Specifically, the special property is that the first $|m'|$ bits of $x_{\text{sol}}$ are $m'$. That is, I will search to find $x_{\text{sol}} = m'\Vert u'$.

Using the slides posted earlier (Slide 8) and their terminology, it is efficient to find a value $x$ from the intersection of two sets $S$ and $P$. Here $S$ is the set of all $x$ such that $H(x) = c$ and $P$ is the set of all $x$ where the first $|m'|$ bits of $x$ are exactly $m'$.

My questions regarding this attack are the following:

1. Did I get the basic idea of the attack correct? If wrong, ignore the rest of the post!

2. How many elements are there in the superposition $\vert\phi\rangle$ after we commit to a certain $c$? In order that I can open the commitment to any message, it seems like I should have $O(N)$ (the size of the hash function's range) elements. But this is too large.

3. The speed of Grover search - this is related to the previous point - is the other thing. Wouldn't the computational complexity of searching over such a large superposition $\vert\phi\rangle$ be the same as trying to guess a pre-image for a given output of the hash function since one has to search over all the $u$? In this case, where is the advantage?

I'm looking for the intuition more than mathematical proofs so any help is greatly appreciated!

Answer 1

Did I get the basic idea of the attack correct? If wrong, ignore the rest of the post!

Mostly. The way you describe it, you will indeed get the state $\lvert\phi\rangle$, but you will not be able to perform the unitary transformation $I-\lvert\phi\rangle\langle\phi\rvert$. But in step 3, when you run Grover on state $\lvert\phi\rangle$, you actually need to apply $I-\lvert\phi\rangle\langle\phi\rvert$ as part of Grover's algorithm. The reason is the following: Usually, Grover is presented as an algorithm that searches a value $x\in\{0,1\}^n$ that satisfies a predicate $P$. In this case, Grover's algorithm first initializes the state to $\lvert\phi\rangle:=\sum_{x\in\{0,1\}^n}2^{-n/2}\lvert x\rangle$. And, during its main loop, it applies the flip operator $I-\lvert\phi\rangle\langle\phi\rvert$. That operator is quite easy to construct if $\lvert\phi\rangle=\sum_{x\in\{0,1\}^n}2^{-n/2}\lvert x\rangle$, so it is normally not mentioned as a requirement of the algorithm. However, instead of searching $x\in\{0,1\}^n$, you could search for $x\in X$ for some set $X$. (After all, there is nothing special about the bitstrings of length $n$.) Then you need to change the description of Grover: The initial state will be $\lvert\phi\rangle=\sum_{x \in X}2^{-\lvert X\rvert/2}\lvert x\rangle$, and we need to apply $I-\lvert\phi\rangle\langle\phi\rvert$ during the main loop. For many sets $X$ (e.g., numbers modulo $N$) it will be fairly easy to construct $\lvert\phi\rangle$ and $I-\lvert\phi\rangle\langle\phi\rvert$. However, in the general case, it might be that it is difficult to construct either of them. In your description of the algorithm, we have a similar situation. Namely, $X=\{x:H(x)=c\}$ for some fixed $c$. But for that set $X$, there is no way to construct $\lvert\phi\rangle$ or $I-\lvert\phi\rangle\langle\phi\rvert$. That's why your algorithm doesn't work (but it still gives the right idea). Instead, in the paper you cite, both $\lvert\phi\rangle$ and $I-\lvert\phi\rangle\langle\phi\rvert$ are provided by special oracles constructed just for this purpose. Using those oracle, you can then run Grovers algorithm on the state $\lvert\phi\rangle$.

How many elements are there in the superposition $\lvert\phi\rangle$ after we commit to a certain $c$?

This will depend on the parameters you chose. We expect roughly $M/N$ if $M$ is the size of the domain and $N$ the size of the range of $H$. For things to be interesting, you should choose $M\gg N$ so that there will be exponentially many elements in the superposition (and at least $2^{\lvert m\rvert}$ so that every message is possible). However, I assume the reason why you are wondering about this is because you think that the number of elements should be small for Grover to work, which is not the case, see below:

The speed of Grover search - this is the main problem and I'm not sure how their trick actually works. Wouldn't the computational complexity be the same as trying to guess a pre-image for a given output of the hash function since one has to search over all the u? In this case, where is the advantage?

Here seems to lie a misconception. Remember my explanations about Grover's algorithm in the beginning of this answer. Grover searches some $x\in X$, satisfying some predicate $P$. In our case $X$ can be huge ($M/N$ elements) because it is the set of all preimages of $c$. But that does not matter. Recall that the original Grover works on $\{0,1\}^n$ which is also huge, but works fast as long as we are searching for some $x\in\{0,1\}^n$ that has some common property $P$. For example, if we search using Grover for $x\in\{0,1\}^n$ that satisfies that $33\mid x$ (the predicate $P$), then we have that there are many $x$'s that satisfy $P$, every 33. $x$ satisfies it! And the runtime will be something like $\sqrt{33}$. So, as a general rule, if a predicate $P$ is satisfied for every $i$-th element of $X$, then Grover's algorithm that searches for $x\in X$ that satisfies $P$ takes about $\sqrt i$ steps. Here it does not matter what set $X$ is, or how big it is! (As long as we have a way to construct $\lvert\phi\rangle$ and $I-\lvert\phi\rangle\langle\phi\rvert$ for this set $X$.) Now, in the setting you describe, $X=\{x:H(x)=c\}$. And $P$ is the predicate saying that $x$ starts with $m'$. To analyze the runtime of Grover's algorithm in this case, we don't care about $X$, but we do need to know how often an element satisfies $P$. That is easy: Every $2^{\lvert m'\rvert}$-th element does. So the runtime of Grover will be $O(\sqrt{2^{\lvert m'\rvert}})$. This is a problem if $m'$ is long, but if $m'$ is, e.g., just a bit, then this works fine. For example, if we use the hash function to commit to one-bit messages, we can open the commitment to any value of $m'$.

If you want an example where $m'$ is longer, then you need to vary the construction. Basically, you commit on every bit individually and concatenate the commitments. Then each commitment can be broken using the method described above, and you need to run the algorithm $\lvert m'\rvert$ times.