**Quantum Multicollision-Finding Algorithm**

*Akinori Hosoyamada and Yu Sasaki and Keita Xagawa*

**Abstract: **The current paper presents a new quantum algorithm for finding multicollisions, often denoted by $l$-collisions, where an $l$-collision for a function is a set of $l$ distinct inputs having the same output value. Although it is fundamental in cryptography, the problem of finding multicollisions has not received much attention \emph{in a quantum setting}. The tight bound of quantum query complexity for finding $2$-collisions of random functions has been revealed to be $\Theta(N^{1/3})$, where $N$ is the size of a codomain. However, neither the lower nor upper bound is known for $l$-collisions. The paper first integrates the results from existing research to derive several new observations, e.g.~$l$-collisions can be generated only with $O(N^{1/2})$ quantum queries for a small constant $l$. Then a new quantum algorithm is proposed, which finds an $l$-collision of any function that has a domain size $l$ times larger than the codomain size. A rigorous proof is given to guarantee that the expected number of quantum queries is $O\left( N^{(3^{l-1}-1)/(2 \cdot 3^{l-1})} \right)$ for a small constant $l$, which matches the tight bound of $\Theta(N^{1/3})$ for $l=2$ and improves the known bounds, say, the above simple bound of $O(N^{1/2})$.

**Category / Keywords: **post-quantum cryptography, multicollision, quantum algorithm, Grover, BHT, rigorous complexity evaluation, state-of-art

**Original Publication**** (in the same form): **IACR-ASIACRYPT-2017

**Date: **received 7 Sep 2017, last revised 7 Sep 2017

**Contact author: **hosoyamada akinori at lab ntt co jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20170913:211316 (All versions of this report)

**Short URL: **ia.cr/2017/864

[ Cryptology ePrint archive ]