Collision Finding
Time, query, and memory complexity of finding collisions – including k-way and other structured collisions – in a random function or permutation.
| Status | Problem | Tags |
|---|---|---|
|
Two-block sponge attack, quadratic advice Open: whether the multi-instance two-block sponge attack of advantage \((S^2T^4/C^2)^S\) lifts to an auxiliary-input attack of advantage \(S^2T^4/C^2\), matching the best proved security bound. Settled in the multi-instance model; no partial result in the auxiliary-input model. 7 open |
Collision FindingCollision Resistant HashingTime Space Tradeoffspromlower-boundadaptation (ai) | |
|
Quantum two-block MD collisions Open, in both directions and with no partial result: whether the best known quantum preprocessing attack, of advantage \(ST^2/N+T^3/N\), is optimal for two-block Merkle-Damgård collisions. The source reports that no matching quantum bounds are known at any block length. 7 open |
Collision FindingCollision Resistant HashingQuantum Query ComplexityQuantum Random Oracle ModelTime Space Tradeoffsqromtight-bound | |
|
3-way collision, oblivious sequential curve Open: closing the factor-\(\sqrt{S}\) gap between the proved oblivious lower bound and a matching table-and-hunt algorithm for finding a 3-way collision with an oblivious sequential branching program. 2 open |
Collision FindingRandom Oracle ModelTime Space Tradeoffsromtight-boundadaptation (ai) | |
|
STB conjecture (Merkle-Damgård) Open for non-constant \(B\) in the regime \(ST^2>2^n\), where the best published security bound and the best published attack are a factor of up to \(S\) apart; settled at \(B=1\), \(B=2\), every constant \(B\), \(B\approx T\), and every \(2<B<T\) with \(ST^2\le 2^n\). 6 open |
Collision FindingCollision Resistant HashingRandom Oracle ModelTime Space Tradeoffsromtight-boundbarrier (ai) | |
|
STB conjecture (sponge) Open for every \(B\ge 2\) except \(B\approx T\): at \(B=2\) in the regime \(ST^3>C\), and at \(B\ge 3\) with a gap of about \(T/B\). The source asks for a proof or a refutation and takes no position. 7 open |
Collision FindingCollision Resistant HashingTime Space Tradeoffspromtight-boundbarrier (ai) | |
|
Tight \(k\)-collision time-space tradeoff The exact tight time-space tradeoff for \(k\ge 3\) collisions under preprocessing is open; only the \(k=2\) case has a matching upper and lower bound. 2 open |
Collision FindingRandom Oracle ModelTime Space Tradeoffsromtight-bound |
No matching items