Specifically, let $D$ be a min-entropy $k$ distribution on a set $Y$ of size $N$. Let $f: X\to Y$ be a function whose output $f(x)$ is drawn according to $D$ for each $x \in X$ independently. We show that $\Omega(2^{k/3})$ quantum queries are necessary to find a collision in $f$, improving the previous bound $\Omega(2^{k/9})$. In fact we show a stronger lower bound $2^{k/2}$ in some special case. For all cases, we also describe explicit quantum algorithms that find a collision with a number of queries matching the corresponding lower bounds.
Category / Keywords: foundations / collision resistance, quantum security, hash functions Date: received 11 Jul 2017, last revised 26 Nov 2017 Contact author: fsong at pdx edu Available format(s): PDF | BibTeX Citation Note: proofs largely updated for modularity; added discussion on preimage and second preimage resistance Version: 20171126:094403 (All versions of this report) Short URL: ia.cr/2017/688