\(k\)-collision time-space tradeoffs under preprocessing
How much does unbounded offline precomputation help an online collision-finder, for k>=3?
Motivation
The auxiliary-input random oracle model (AI-ROM) captures adversaries who get unbounded offline precomputation time before facing an online query budget – a realistic model for attacks amortized over many targets (e.g. building a rainbow table once, attacking many instances). The 2-collision tradeoff is fully understood; pinning down the general \(k\)-collision tradeoff would complete the picture for multi-target collision resistance under preprocessing.
Provenance and history
The tight 2-collision bound \(S \cdot T^2 = \Theta(N)\) combines a matching attack and lower bound (Hellman, 1980; Coretti et al., 2018). For \(k \ge 3\), the best known attack achieves \(S^{k-1}T^k = O(N^{k-1})\) while the best known lower bound is only \(S \cdot T^k = \Omega(N)\), leaving a gap of a full factor of \(S^{k-2}\) that current compression-argument and bit-fixing techniques don’t close.
Parameter lattice
The axis of variation is the collision multiplicity \(k\).
| \(k\) | Lower bound | Best known attack | Status |
|---|---|---|---|
| \(k = 2\) | \(S \cdot T^2 = \Omega(N)\) | \(S \cdot T^2 = O(N)\) | Tight (cited result, not a leaf here) |
| \(k = 3\) | \(S \cdot T^3 = \Omega(N)\) | \(S^2 \cdot T^3 = O(N^2)\) | Gap of \(S\) |
| general \(k \ge 3\) | \(S \cdot T^k = \Omega(N)\) | \(S^{k-1}T^k = O(N^{k-1})\) | c/0003 – open |