Welcome to the resource topic for 2025/1550
Title:
Revisiting Time-Space Tradeoffs in Collision Search and Decision Problems
Authors: Jian Guo, Wenjie Nan, Yiran Yao
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.
ePrint: https://eprint.iacr.org/2025/1550
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .