**Improved Quantum Multicollision-Finding Algorithm**

*Akinori Hosoyamada and Yu Sasaki and Seiichiro Tani and Keita Xagawa*

**Abstract: **The current paper improves the number of queries of the previous quantum multi-collision finding algorithms presented by Hosoyamada et al. at Asiacrypt 2017. Let an $l$-collision be a tuple of $l$ distinct inputs that result in the same output of a target function. In cryptology, it is important to study how many queries are required to find $l$-collisions for random functions of which domains are larger than ranges. The previous algorithm finds an $l$-collision for a random function by recursively calling the algorithm for finding $(l-1)$-collisions, and it achieves the average quantum query complexity of $O(N^{(3^{l-1}-1) / (2 \cdot 3^{l-1})})$, where $N$ is the range size of target functions. The new algorithm removes the redundancy of the previous recursive algorithm so that different recursive calls can share a part of computations. The new algorithm finds an $l$-collision for random functions with the average quantum query complexity of $O(N^{(2^{l-1}-1) / (2^{l}-1)})$, which improves the previous bound for all $l\ge 3$ (the new and previous algorithms achieve the optimal bound for $l=2$). More generally, the new algorithm achieves the average quantum query complexity of $O\left(c^{3/2}_N N^{\frac{2^{l-1}-1}{ 2^{l}-1}}\right)$ for a random function $f\colon X\to Y$ such that $|X| \geq l \cdot |Y| / c_N$ for any $1\le c_N \in o(N^{\frac{1}{2^l - 1}})$. With the same query complexity, it also finds a multiclaw for random functions, which is harder to find than a multicollision.

**Category / Keywords: **foundations / post-quantum cryptography, quantum algorithm, multiclaw, multicollision

**Original Publication**** (in the same form): **PQCrypto 2019

**Date: **received 18 Nov 2018, last revised 28 Jan 2019

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

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

**Version: **20190128:092621 (All versions of this report)

**Short URL: **ia.cr/2018/1122

[ Cryptology ePrint archive ]