The NISQ Complexity of Collision Finding

Collision-resistant hashing, a fundamental primitive in modern cryptography, ensures that there is no efficient way to find distinct inputs that produce the same hash value. This property underpins the security of various cryptographic applications, making it crucial to understand its complexity. The complexity of this problem is well-understood in the classical setting and Θ(N^1/2) queries are needed to find a collision. However, the advent of quantum computing has introduced new challenges since quantum adversaries—equipped with the power of quantum queries—can find collisions much more efficiently. Brassard, Høyer and Tapp [15] and Aaronson and Shi [3] established that full-scale quantum adversaries require Θ(N^1/3) queries to find a collision, prompting a need for longer hash outputs, which impacts efficiency in terms of the key lengths needed for security. This paper explores the implications of quantum attacks in the Noisy-Intermediate Scale Quantum (NISQ) era. In this work, we investigate three different models for NISQ algorithms and achieve tight bounds for all of them: A hybrid algorithm making adaptive quantum or classical queries but with a limited quantum query budget, orA quantum algorithm with access to a noisy oracle, subject to a dephasing or depolarizing channel, orA hybrid algorithm with an upper bound on its maximum quantum depth; i.e. a classical algorithm aided by low-depth quantum circuits. A hybrid algorithm making adaptive quantum or classical queries but with a limited quantum query budget, or A quantum algorithm with access to a noisy oracle, subject to a dephasing or depolarizing channel, or A hybrid algorithm with an upper bound on its maximum quantum depth; i.e. a classical algorithm aided by low-depth quantum circuits. In fact, our results handle all regimes between NISQ and full-scale quantum computers. Previously, only results for the preimage search problem were known for these models (by Sun and Zheng [50], Rosmanis [45, 46], Chen, Cotler, Huang and Li [17]) while nothing was known about the collision finding problem. Along with our main results, we develop an information-theoretic framework for recording query transcripts of quantum-classical algorithms. The main feature of this framework is that it allows us to record queries in two incompatible bases—classical queries in the standard basis and quantum queries in the Fourier basis—consistently. We call the framework the hybrid compressed oracle as it naturally interpolates between the classical way of recording queries and the compressed oracle framework of Zhandry for recording quantum queries. We demonstrate its applicability by giving simpler proofs of the optimal lower bounds for NISQ preimage search and by showing optimal lower bounds for NISQ collision finding.