Collision resistance and collision finding are now extensively exploited in Cryptography, especially in the case of quantum computing. For any function \(f:[M]\rightarrow [N]\) with f(x) uniformly distributed over [N], Zhandry has shown that the number \(\varTheta (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 the 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 expectedly uses \(O(\gamma ^{1/6})\) quantum queries to find a collision for any non-uniform random function. By transforming a problem in a non-uniform setting into a problem in a uniform setting, we are also able to show that \(\varOmega (\gamma ^{1/6}\log ^{-1/2}\gamma )\) quantum queries are necessary for collision-finding in any non-uniform random function. The upper bound and the lower bound in this work indicate that the proposed algorithm is nearly optimal with query complexity in the general non-uniform case.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Tianci Peng,
  • Shujiao Cao,
  • 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]\rightarrow [N]\) with f(x) uniformly distributed over [N], Zhandry has shown that the number \(\varTheta (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 the 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 expectedly uses \(O(\gamma ^{1/6})\) quantum queries to find a collision for any non-uniform random function. By transforming a problem in a non-uniform setting into a problem in a uniform setting, we are also able to show that \(\varOmega (\gamma ^{1/6}\log ^{-1/2}\gamma )\) quantum queries are necessary for collision-finding in any non-uniform random function. The upper bound and the lower bound in this work indicate that the proposed algorithm is nearly optimal with query complexity in the general non-uniform case.