You are looking at a specific version 20211203:075807 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.