International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On Quantum Query Complexities of Collision-Finding in Non-Uniform Random Functions

Authors:
Tianci Peng , State Key Laboratory of Cyberspace Security Defense Institute of Information Engineering, CAS; School of Cyber Security, University of CAS
Shujiao Cao , State Key Laboratory of Cyberspace Security Defense Institute of Information Engineering, CAS; School of Cyber Security, University of CAS
Rui Xue , State Key Laboratory of Cyberspace Security Defense Institute of Information Engineering, CAS; School of Cyber Security, University of CAS
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2025
Abstract: Collision resistance and collision finding are now extensively exploited in Cryptography, especially in the case of quantum computing. For any function $f:[M]\to[N]$ with $f(x)$ uniformly distributed over $[N]$, Zhandry has shown that the number $\Theta(N^{1/3})$ of queries is both necessary and sufficient for finding a collision in $f$ with constant probability. However, there is still a gap between the upper and the lower bounds of query complexity in general non-uniform distributions. In this paper, we investigate the quantum query complexity of the collision-finding problem with respect to general non-uniform distributions. Inspired by previous work, we pose the concept of collision domain and a new parameter $\gamma$ that heavily depends on the underlying non-uniform distribution. We then present a quantum algorithm that uses $O(\gamma^{1/6})$ quantum queries to find a collision for any non-uniform random function. By transforming a problem in a non-uniform setting into a problem in a uniform setting, we are also able to show that $\Omega(\gamma^{1/6}\log^{-1/2}\gamma)$ quantum queries are necessary for collision-finding in any non-uniform random function. The upper bound and the lower bound in this work indicate that the proposed algorithm is nearly optimal with query complexity in the general non-uniform case.
BibTeX
@inproceedings{asiacrypt-2025-35912,
  title={On Quantum Query Complexities of Collision-Finding in Non-Uniform Random Functions},
  publisher={Springer-Verlag},
  author={Tianci Peng and Shujiao Cao and Rui Xue},
  year=2025
}