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

Abstract

Abstract 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})$$ O ( γ 1 / 6 ) and a matching lower bound of $$\tilde{\Omega }(\gamma ^{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_1,\dots , x_s$$ x 1 , ⋯ , x s such that $$f(x_1)=f(x_2)\dots =f(x_s)$$ f ( x 1 ) = f ( x 2 ) ⋯ = f ( x s ) . In this work, we address this challenge by similarly introducing a new generalized parameter $$\gamma _s$$ γ s . Based on this parameter, we establish nearly tight bounds—an upper bound of $$O(\gamma _s)$$ O ( γ s ) and a lower bound of $$\tilde{\Omega }(\gamma _s)$$ Ω ~ ( γ 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.