Paper 2021/1578

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

Tianci Peng, Shujiao Cao, and Rui Xue


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 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 making a transformation of a problem in non-uniform setting into a problem in uniform setting, we are also able to show that $\Omega(\gamma^{1/6}\log^{-1/2}\gamma)$ quantum queries are necessary in collision-finding in any non-uniform random function. The upper bound and the lower bound in this work indicates that the proposed algorithm is nearly optimal with query complexity in general non-uniform case.

Available format(s)
Publication info
Preprint. MINOR revision.
QuantumQuery complexityCollision-finding algorithmCompressed oracle techniqueNon-uniform distributionLower bound
Contact author(s)
pengtianci @ iie ac cn
caoshujiao @ iie ac cn
xuerui @ iie ac cn
2021-12-03: received
Short URL
Creative Commons Attribution


      author = {Tianci Peng and Shujiao Cao and Rui Xue},
      title = {On Quantum Query Complexities of Collision-Finding in Non-Uniform Random Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1578},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.