Paper 2021/1578
On Quantum Query Complexities of Collision-Finding in Non-Uniform Random Functions
Tianci Peng and 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.
Metadata
- 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
- 2023-02-02: revised
- 2021-12-03: received
- See all versions
- Short URL
- https://ia.cr/2021/1578
- License
-
CC BY