On finding quantum multi-collisions in non-uniform random functions

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 γ γ . Based on this parameter, they established an upper bound of O(γ 1/6) O ( γ 1 / 6 ) and a matching lower bound of Ω ̃(γ 1/6) Ω ~ ( γ 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₁, , xₛ x 1 , ⋯ , x s such that f(x₁)=f(x₂) =f(xₛ) f ( x 1 ) = f ( x 2 ) ⋯ = f ( x s ) . In this work, we address this challenge by similarly introducing a new generalized parameter γ ₛ γ s . Based on this parameter, we establish nearly tight bounds—an upper bound of O(γ ₛ) O ( γ s ) and a lower bound of Ω ̃(γ ₛ) Ω ~ ( γ 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$$ 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.