Tight Time-Space Lower Bounds for Finding Multiple Collision Pairs and Their Applications
We consider a collision search problem (CSP), where given a parameter C, the goal is to find C collision pairs in a random function \(f:[N] \rightarrow [N]\) (where \([N] = \{0,1,\ldots ,N-1\})\) using S bits of memory. Algorithms for CSP have numerous cryptanalytic applications such as space-efficient attacks on double and triple encryption. The best known algorithm for CSP is parallel collision search (PCS) published by van Oorschot and Wiener, which achieves the time-space tradeoff \(T^2 \cdot S = \tilde{O}(C^2 \cdot N)\).