A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, \(\varTheta \left( N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right) \) quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.
A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, (\varTheta \left( N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right) ) quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.
A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, Θ(N21(1−2k−11)) quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.
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 γ γ . 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 x1,…,xs x 1 , ⋯ , x s such that f(x1)=f(x2)⋯=f(xs) f ( x 1 ) = f ( x 2 ) ⋯ = f ( x s ) . In this work, we address this challenge by similarly introducing a new generalized parameter γs γ s . Based on this parameter, we establish nearly tight bounds—an upper bound of O(γs) O ( γ s ) and a lower bound of Ω~(γ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.
A collision for a function f is two distinct inputs x1=x2 such that f outputs the same value on both inputs: f(x1)=f(x2). The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be Θ(N1/3); however, these results do not apply to random functions. The issues are two-fold. First, the Ω(N1/3) lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to r-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of Θ(N1/3) holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal Ω(M1/3) lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.
This work proves an improved lower bound for the quantum query complexity of collision- finding in hash functions whose images are distributed according to a non-uniform distribution. Recent work by [TTU16] applied the leftover hash lemma to show that at least Omega(2k/9) quantum queries are necessary to find a collision when the image distribution has min-entropy k. In comparison, a result by [Zha15] implies that Omega(2k/3) quantum queries are necessary if the distribution is uniform. In this paper the lower bound complexity of [Zha15] is extended directly to the non-uniform case using a chain of reductions which convert collisions in min-entropy k distributions into collisions in the uniform distribution with constant probability. This result shows a minimum security guarantee for hash functions under more general assumptions in which the image distribution may not be uniform.
How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function f:[N]→[N], the BHT algorithm finds a collision using O(N1/3) queries and a quantumly accessible classical table containing O(N1/3) input-output pairs, whereas a logarithmic-space Grover search uses O(N) queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem.
We resolve this equation within the class of label-symmetric algorithms, which treat the function f's output labels as interchangeable. We prove that such algorithm that makes T queries, uses S qubits, and finds a collision in a uniformly random function f:[M]→[N] with constant probability satisfies T=Ω(N1/3)andT2S=Ω(NlogN). For the setting where M=N, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on f:[n]→[n2] must satisfy T=Ω(n2/3)andT2S=Ω(n2logn), matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms.
To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using S qubits can effectively retain information about only O(S/logN) collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.