Tight Time-Space Tradeoffs for \(k\)-Collisions with Auxiliary Input

–

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

View PDF · Download LaTeX source

Abstract

Finding collisions in hash functions under preprocessing (the Random Oracle Model with Auxiliary Input, AI-ROM) models realistic adversaries who execute unbounded offline computation to store an \(S\)-bit summary of a random oracle \(H : [N] \to [N]\). While the exact tight tradeoff for 2-collisions (\(k=2\)) is established as \(S \cdot T^2 = \Theta(N)\), determining the exact asymptotic curve \(S^a T^b = \Omega(N^c)\) for multicollisions (\(k \ge 3\)) remains an open problem in provable security.

Formal Model: AI-ROM

Let \(H : [N] \to [N]\) be a uniformly random function, where \(N = 2^n\).

NoteDefinition (\(k\)-Collision Finding with Precomputation)

A two-stage adversary \(\mathcal{A} = (\mathcal{A}_1, \mathcal{A}_2)\) operates as follows:

  1. Offline Phase: \(\mathcal{A}_1^H(1^n)\) has unbounded access to \(H\) and outputs an advice string \(S \in \{0,1\}^S\) of size at most \(S\) bits.
  2. Online Phase: \(\mathcal{A}_2^H(S)\) receives \(S\), makes at most \(T\) query evaluations to \(H\), and outputs a tuple of \(k\) distinct inputs \((x_1, x_2, \dots, x_k)\).

The adversary wins if \(H(x_1) = H(x_2) = \dots = H(x_k)\) and \(x_i \neq x_j\) for all \(1 \le i < j \le k\).

The Open \(k\)-Collision Tradeoff Conjecture

ImportantConjecture (Tight \(k\)-Collision Time-Space Tradeoff)

Let \(H : [N] \to [N]\) be a random oracle. For any \(k \ge 3\), any adversary \((\mathcal{A}_1, \mathcal{A}_2)\) with \(S\)-bit advice and \(T\) online queries that finds a \(k\)-collision with success probability \(\epsilon \ge 1/2\) must satisfy:

\[ S^{k-1} \cdot T^{k} \ge \Omega\left( N^{k-1} \right). \]

Specifically, for 3-collisions (\(k=3\)), the optimal trade-off satisfies:

\[ S^2 \cdot T^3 \ge \Omega\left( N^2 \right). \]

Comparison of Known Upper and Lower Bounds

Current state of knowledge for precomputation bounds in AI-ROM.
Collision Multiplicity (\(k\)) Known Lower Bound Best Known Attack (Upper Bound) Status
\(k = 2\) (2-Collision) \(S \cdot T^2 = \Omega(N)\) \(S \cdot T^2 = O(N)\) (Hellman, 1980 / Coretti et al., 2018) Tight
\(k = 3\) (3-Collision) \(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})\) OPEN

Why the problem is hard: current lower-bound techniques (such as compression arguments or the bit-fixing model) fail to capture the multi-way combinatorial synergy when \(S\) advice bits store structural information about hypergraphs of preimages across \(k\) distinct points simultaneously.

This conjecture is open — no proof exists yet.

Once (an attempt at) a proof exists, add its own .tex source and compiled PDF (e.g. latex/proof.tex / pdf/proof.pdf) and link them here, following the same convention as the statement.

Formal artifact.

Lean statement — autoformalized by Claude Sonnet 5; not yet checked by a human against the tex statement above.

Only the conjecture’s statement has been formalized so far (as a Lean theorem ending in sorry — see lean/Statement.lean), not a proof. Once a proof exists, set status.proof_informal/status.proof_review/status.proof_formal accordingly and regenerate the badge with scripts/status_badge.py.

The \(k = 2\) case is settled at \(S \cdot T^2 = \Theta(N)\), and the conjecture is that the curve for \(k \ge 3\) is the natural extrapolation of it. What makes that non-obvious is that the offline stage is unbounded: the advice string may encode any function of the whole oracle, so a tight bound has to hold against preprocessing that is not query-bounded at all, which is exactly what presampling techniques were built to handle and what limits how far they reach.

Nothing beyond this has been written here; see the problem page for the surrounding results.