Improved Quantum Multicollision-Finding Algorithm

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 lge 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 Oleft\(c^3/2_N N^{frac{2^l-1-1}{ 2^l-1}}right\) for a random function fcolon X→ Y such that |X| geq l cdot |Y| / c_N for any 1le 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.