Paper 2025/1550

Revisiting Time-Space Tradeoffs in Collision Search and Decision Problems

Wenjie Nan, Nanyang Technological University

Yiran Yao, Nanyang Technological University

Abstract

We present analysis of time-space tradeoffs for both the search and decision variants of the $k$-collision problem in algorithmic perspective, where $k \in \left[2, O(\operatorname{polylog}(N))\right]$ and the underlying function is $f_{N,M} : [N] \rightarrow [M]$ with $M \geq N$. In contrast to prior work that focuses either on 2-collisions or on random functions with $M = N$, our results apply to both random and arbitrary functions and extend to a broader range of $k$. The tradeoffs are derived from explicit algorithmic constructions developed in this work, especially for decision problems when $k\geq3$. For 2-collision problems, we show that for any random function $f_{N,M}$ with $M \geq N$, the time-space tradeoff for finding all 2-collisions follows a single curve $T=\widetilde{O}\left(\frac{N^{3/2}}{\sqrt{S}}\right)$, where $T$ denotes time complexity and $S$ denotes available space. This tradeoff also extends to arbitrary functions with at most $O(N)$ total 2-collisions. For 3-collision problems, we identify two time-space tradeoff curves for the search variant over random functions, depending on the available space $S$. For arbitrary functions, we show that the decision problem can be solved with a tradeoff of $T=\widetilde{O}\left(\frac{N^{3/2}}{\sqrt{S}} + \frac{N}{S}\frac{n_2}{n_3}\right)$, where $n_{i}$ denotes the number of $i$-collisions. Surprisingly, for random functions, the decision problem for 3-collision shares the same time-space tradeoff as the 2-collision case $T=\widetilde{O}\left(\frac{N^{3/2}}{\sqrt{S}}\right)$. For general $k$-collision problems, we extend these results to show that the decision problem over arbitrary functions can be solved in time $T=\widetilde{O}\left(\frac{N^{3/2}}{\sqrt{S}} + \frac{N}{S}\frac{n_2}{n_k}\right)$. For the search problem over random functions, we derive two time-space tradeoffs based on the space $S$, yielding approximately $S^{1/(k-2)}$ or $S^{1/(2k-2)}$-fold speedups compared to the low-memory setting $S = O(\log M)$. When $M = N$, the tradeoff simplifies to one single curve with $S^{1/(k-2)}$-fold speedup.

@misc{cryptoeprint:2025/1550,
      author = {Jian Guo and Wenjie Nan and Yiran Yao},
      title = {Revisiting Time-Space Tradeoffs in Collision Search and Decision Problems},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1550},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1550}
}