Collision Finding
Time, query, and memory complexity of finding collisions – including k-way and other structured collisions – in a random function or permutation.
| Status | Statement | Tags |
|---|---|---|
|
Two-block sponge attack, quadratic advice Open: whether the multi-instance two-block sponge attack of advantage (S2T4/C2)S lifts to an auxiliary-input attack of advantage S2T4/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-root-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~T, and every 2<B<T with ST^2 <= 2^n. 6 open |
Collision FindingCollision Resistant HashingRandom Oracle ModelTime Space Tradeoffsromtight-boundbarrier (ai) | |
|
STB conjecture (sponge) Open for every B >= 2 except B ~ T: at B=2 in the regime ST^3 > C, and at B >= 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>=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