Quantum Random Oracle Model

Question

Let $\mathcal{H} : \{0,1\}^* \rightarrow \{1,\cdots,n\}$ be a hash function.

I believe that in the Random Oracle model, the probability that an adversary $A$ can find a message $M$ such that $\mathcal{H}(M) \leq k$ is at most $(q+1) \frac{k}{n}$, where $q$ is the number of queries $A$ makes to $\mathcal{H}$.

What happens for a quantum adversary $B$, which can query $\mathcal{H}$ in superposition? I suspect that the probability that $B$ produces a message $M$ such that $\mathcal{H}(M)\leq k$ is bounded by $c q^2 \frac{k}{n}$, where $q$ i the number of quantum queries that $B$ makes to $\mathcal{H}$ and $c$ some constant.

I suspect this because this can be done with Grover's algorithm and I heard that Grover's Algorithm is optimal in some setting.

Is this true? What values of $c$ would work? How would you prove this?

Answer 1

You are right, the success probability of a $q$-query quantum adversary is $\Theta(\frac{k(q+1)^2}{n})$. You can find a proof of the upper and lower bound in this paper.

The upper bound uses similar tools as for the optimality of Grover. The tricky part is that the proof of optimality for Grover's algorithm is given for the worst-case but I guess you and people in crypto in general are mainly interested in the average case complexity. So you need a more advanced toolkit.

The lower bound is more or less applying Grover and analysing its success probability for the average case.