Paper 2026/2694

Quantum Time-Space Tradeoffs for Short Merkle-Damgård Collisions

Abstract

We study time-space tradeoffs for finding short collisions in Merkle-Damg{\aa}rd~(MD) hashing in the quantum auxiliary-input quantum random-oracle model~(QAI-QROM). An adversary may preprocess the compression function into $S$ qubits of arbitrary oracle-dependent quantum advice and, after receiving a fresh salt, make $T$ superposition queries to find a collision consisting of at most $B$ blocks. Previous quantum analyses gave an $\widetilde{O}(ST^3/N)$ security bound for MD collisions with classical advice. Unlike the classical theory of short MD collisions, however, this bound is insensitive to the collision length $B$: existing quantum techniques did not exploit the combinatorial structure forced by a short collision. We develop a structure-sensitive compressed-oracle analysis that overcomes this obstacle. For two-block collisions, we prove an upper bound \[ \widetilde{O}\left(\min\left\{1, \frac{ST^2+T^3}{N}\right\}\right), \] even against arbitrary quantum advice. For $M=N$, together with the known attack, this gives a tight characterization up to logarithmic factors, closes the previous factor-$T$ gap in the preprocessing term, and resolves an open problem of Akshima, Guo, and Liu~(CRYPTO '22, JoC '24). For general $B\le T$, we show in the regime $(2S+1)(T+2B)^3\le N$ that the success probability is at most \[ \widetilde{O}\!\left(\min\left\{1, \frac{ST^2B+T^3}{N}\right\}\right). \] Thus, when $B\ll T$, the preprocessing term improves over the previous $ST^3/N$ bound by a factor of roughly $T/B$. Motivated by the tight two-block result, we propose the $ST^2B$ conjecture, asserting that $ST^2B=\widetilde{\Theta}(N)$ is the correct constant-success tradeoff for short MD collisions in the regime $T^3=o(N)$.