Collision resistance is one of the most fundamental properties in cryptography. With the development of quantum computing, significant attention has been directed toward understanding the quantum query complexity of collision-finding problems in hash functions. The quantum query complexity of collision-finding in general non-uniform random functions remained an open problem until the recent work of Peng et al. (ASIACRYPT 2025), who nearly resolved it by introducing a novel parameter \(\gamma\) . Based on this parameter, they established an upper bound of \(O(\gamma ^{1/6})\) and a matching lower bound of \(\tilde{\Omega }(\gamma ^{1/6})\) . However, the quantum query complexity of finding multi-collisions in non-uniform random functions has remained open. A s-collision to a function f is a set of distinct input \(x_1,\dots , x_s\) such that \(f(x_1)=f(x_2)\dots =f(x_s)\) . In this work, we address this challenge by similarly introducing a new generalized parameter \(\gamma _s\) . Based on this parameter, we establish nearly tight bounds—an upper bound of \(O(\gamma _s)\) and a lower bound of \(\tilde{\Omega }(\gamma _s)\) —thereby nearly resolving this open problem. Moreover, although the existing results for 2-collisions do not generalize straightforwardly to the case of s-collision ( \(s>2\) ), we demonstrate that the result of Peng et al. can be viewed as a special case of our more general framework. This clearly establishes our work as a direct generalization of their contribution.
