Collision Resistant Hashing

Collision-resistant hash functions as a primitive, and their relations to other assumptions.

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 Finding Collision Resistant Hashing Time 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 Finding Collision Resistant Hashing Quantum Query Complexity Quantum Random Oracle Model Time Space Tradeoffsqromtight-bound
	SBP Collision Resistance Posed as a displayed Open Question and called a central open challenge. The source gives an efficient online collision finder for small \(\kappa\) and an overlap-gap-based online lower bound for a different, randomized activation – introduced precisely because the SBP’s own collision space resists a first-moment analysis. For very large \(\kappa\) collisions become trivial. The middle window is reached by neither technique. 4 open	Average Case Hardness Collision Resistant Hashing Overlap Gap Property Planted Constraint Satisfactionseparation
	OWFs are black-box helpful for CRHFs Open in both directions. Two relaxations — distributional and class-reduction helpfulness — are proved conditional on the Simon-oracle amplification conjecture; neither yields the universal auxiliary primitive the full statement needs. 4 open	Black Box Separations Collision Resistant Hashing One Way Functionsotherseparation
	Simon-oracle amplification, strong version Open. The version without the collision finder is known only when the one-way function is itself a random oracle; with an arbitrary one-way function, with or without the collision finder, nothing is established. 5 open	Black Box Separations Collision Resistant Hashing One Way Functionsotherlower-bound
	CHV Online Threshold Conjecture 1 of the source, its online threshold conjecture. The source gives an online algorithm achieving \(\kappa=O(\sqrt{\alpha}/B)\) and an overlap-gap argument against stable algorithms; the conjecture pins the constant \(\sqrt{\pi/8}\) as the exact place where online algorithms stop. Separately it proves, under worst-case lattice hardness, that no polynomial-time algorithm solves CHV for \(\kappa=O(1/(B n^{1/2+\varepsilon}))\). 4 open	Average Case Hardness Collision Resistant Hashing Locality Preserving Hashing Overlap Gap Propertytight-bound
	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 Finding Collision Resistant Hashing Random Oracle Model Time 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 Finding Collision Resistant Hashing Time Space Tradeoffspromtight-boundbarrier (ai)