A Tight Quantum Algorithm for Multiple Collision Search

• URL: http://arxiv.org/abs/2509.13909v1
• Date: Wed, 17 Sep 2025 11:15:02 GMT
• Title: A Tight Quantum Algorithm for Multiple Collision Search
• Abstract summary: Searching for collisions in random functions is a fundamental computational problem.<n>We give a new algorithm that tackles the remaining non-optimal range, closing the problem.<n>Our algorithm is tight (up to a factor) in queries, and also in time under a quantum RAM assumption.
• Score: 4.913876853745498
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Searching for collisions in random functions is a fundamental computational problem, with many applications in symmetric and asymmetric cryptanalysis. When one searches for a single collision, the known quantum algorithms match the query lower bound. This is not the case for the problem of finding multiple collisions, despite its regular appearance as a sub-component in sieving-type algorithms. At EUROCRYPT 2019, Liu and Zhandry gave a query lower bound $\Omega(2^{m/3 + 2k/3})$ for finding $2^k$ collisions in a random function with m-bit output. At EUROCRYPT 2023, Bonnetain et al. gave a quantum algorithm matching this bound for a large range of $m$ and $k$, but not all admissible values. Like many previous collision-finding algorithms, theirs is based on the MNRS quantum walk framework, but it chains the walks by reusing the state after outputting a collision. In this paper, we give a new algorithm that tackles the remaining non-optimal range, closing the problem. Our algorithm is tight (up to a polynomial factor) in queries, and also in time under a quantum RAM assumption. The idea is to extend the chained walk to a regime in which several collisions are returned at each step, and the ``walks'' themselves only perform a single diffusion layer.

Related papers

• Pseudo-deterministic Quantum Algorithms [7.46931129146594]
  We show that for any total problem $R$, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms.<n>On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead.
  arXiv  Detail & Related papers  (2026-02-19T18:54:47Z)
• Distributed quantum algorithm for divergence estimation and beyond [12.925989807145301]
  We propose a distributed quantum algorithm framework to compute $rm Tr(f(A)g(B))$ within an additive error $varepsilon$.<n>This framework holds broad applicability across a range of distributed quantum computing tasks.
  arXiv  Detail & Related papers  (2025-03-12T14:28:22Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms.<n>Intrepid permutations have so far remained a fundamental open problem.<n>We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• The NISQ Complexity of Collision Finding [2.9405711598281536]
  A fundamental primitive in modern cryptography, collision-resistant hashing ensures there is no efficient way to find inputs that produce the same hash value. Quantum adversaries now require full-scale computers equipped with the power of NISQ. In this paper, we investigate three different models for NISQ algorithms achieve tight bounds for all of them.
  arXiv  Detail & Related papers  (2022-11-23T13:55:28Z)
• Optimal exact quantum algorithm for the promised element distinctness problem [0.2741266294612775]
  An element distinctness problem is to determine whether a string $x=(x_1,ldots,x_N)$ of $N$ elements contains two elements of the same value. We propose an exact quantum algorithm for the promise problem which never errs and requires $O(N2/3)$ queries.
  arXiv  Detail & Related papers  (2022-11-10T09:33:13Z)
• Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
  Collision finding is an ubiquitous problem in cryptanalysis. In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters. As an application, we improve the quantum sieving algorithms for the shortest vector problem.
  arXiv  Detail & Related papers  (2022-05-27T14:50:45Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.