Welcome to the resource topic for 2021/1578
Title:
On Quantum Query Complexities of Collision-Finding in Non-Uniform Random Functions
Authors: Tianci Peng, Shujiao Cao, 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.
ePrint: https://eprint.iacr.org/2021/1578
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .