Collision Resistant Hashing

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

Status	Statement	Tags
	Two-block sponge attack, quadratic advice Open: whether the multi-instance two-block sponge attack of advantage (S^2T4/C²⁾S lifts to an auxiliary-input attack of advantage S^2T4/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+eps))). 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~T, and every 2<B<T with ST^2 <= 2^n. 6 open	Collision Finding Collision Resistant Hashing Random Oracle Model Time 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 Finding Collision Resistant Hashing Time Space Tradeoffspromtight-boundbarrier (ai)