Paper 2018/1122

Improved Quantum Multicollision-Finding Algorithm

Akinori Hosoyamada, Yu Sasaki, 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 $$-collision for random functions with the average quantum query complexity of $$, which improves the previous bound for all $$ (the new and previous algorithms achieve the optimal bound for $$). More generally, the new algorithm achieves the average quantum query complexity of $$ for a random function $$ such that $$ for any $$. With the same query complexity, it also finds a multiclaw for random functions, which is harder to find than a multicollision.