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

Tianci Peng, Shujiao Cao, and Rui Xue

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 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)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
QuantumQuery complexityCollision-finding algorithmCompressed oracle techniqueNon-uniform distributionLower bound
Contact author(s)
pengtianci @ iie ac cn
caoshujiao @ iie ac cn
xuerui @ iie ac cn
History
Short URL
https://ia.cr/2021/1578

CC BY

BibTeX

@misc{cryptoeprint:2021/1578,
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{https://eprint.iacr.org/2021/1578}},
url = {https://eprint.iacr.org/2021/1578}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.