One-Way Functions Are Fully Black-Box Helpful for Collision-Resistant Hashing

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

Simon proved that collision-resistant hashing cannot be built from one-way functions in a black-box way. This asks the composed question: is a one-way function not merely insufficient, but useless — never turning an inadequate auxiliary primitive into an adequate one? The paper conjectures no. It conjectures that some auxiliary primitive \(\mathcal{Z}\) exists from which collision resistance cannot be built, but from which it can once any one-way function is added. That would be the first natural inhabitant of the gap between separation and uselessness, and would explain how one-way functions might yet appear in a future construction of collision resistance from apparently weaker ingredients.

View PDF · Download LaTeX source

A cryptographic primitive is a pair \(\mathcal{P} = (F_{\mathcal{P}}, R_{\mathcal{P}})\), where \(F_{\mathcal{P}}\) is the set of functions implementing \(\mathcal{P}\) and \((\mathsf{P}, A) \in R_{\mathcal{P}}\) means the adversary \(A\) breaks the implementation \(\mathsf{P}\); at least one implementation must be PPT-computable. The joint primitive \((\mathcal{P}, \mathcal{Q})\) has implementations \(F_{\mathcal{P}} \times F_{\mathcal{Q}}\) and is broken when either component is.

A fully black-box reduction of \(\mathcal{P}\) to \(\mathcal{Q}\) is a pair \((\mathsf{P}, \mathsf{S})\) of oracle-aided PPT machines such that for every \(\mathsf{Q} \in F_{\mathcal{Q}}\): \(\mathsf{P}^{\mathsf{Q}} \in F_{\mathcal{P}}\), and every \(A\) breaking \(\mathsf{P}^{\mathsf{Q}}\) makes \(\mathsf{S}^{\mathsf{Q},A}\) break \(\mathsf{Q}\).

\(\mathcal{Q}\) is fully black-box helpful for \(\mathcal{P}\) if some auxiliary primitive \(\mathcal{Z}\) makes \((\mathcal{Q}, \mathcal{Z})\) fully black-box imply \(\mathcal{P}\) while \(\mathcal{Z}\) alone does not. This is the negation of \(\mathcal{Q}\) being fully black-box useless for \(\mathcal{P}\).

Conjecture. There exists a cryptographic primitive \(\mathcal{Z}\) such that (i) there is a fully black-box reduction of \(\mathcal{CRH}\) to the joint primitive \((\mathcal{F}, \mathcal{Z})\), and (ii) there is no fully black-box reduction of \(\mathcal{CRH}\) to \(\mathcal{Z}\) alone. Equivalently, the primitive \(\mathcal{F}\) of one-way functions is fully black-box helpful for the primitive \(\mathcal{CRH}\) of collision-resistant hash functions.

Two things in the transcription are the drafter’s rather than the paper’s, and are flagged as such in the LaTeX. The paper gives no definition of collision-resistant hashing at all — its preliminaries define one-way functions, key agreement and obfuscation only — so the syntax of \(\mathcal{CRH}\), and with it the compression ratio, is supplied here and deliberately generic. And the unfolding of “black-box helpful” to the level of primitives is a reconstruction from a section the paper itself calls “a relatively informal discussion”, though it matches the paper’s informal definition and its formal distributional analogue.

Open, and open in both directions.

Why the obvious route to a refutation is blocked. Refuting the conjecture means proving that one-way functions are black-box useless for collision resistance. Simon’s separation is an oracle separation — a random permutation \(\pi\) together with an oracle \(\mathsf{Coll}^{\pi}\) returning collisions for any circuit built from it — and the paper’s uselessness results all lift compiling-out separations, which this is not. In the authors’ words, “it is not clear how one would extend Simon’s strategy”; they conjecture the failure is inherent.

The first route to a proof. Take \(\mathcal{Z}\) to be Simon’s pair \((\pi, \mathsf{Coll}^{\pi})\) itself. Holmgren and Lombardi proved that exponentially secure one-way product functions black-box imply collision-resistant hashing, so it would suffice to show that for every one-way function \(\mathsf{F}\) the pair \((\mathsf{F}, (\pi, \mathsf{Coll}^{\pi}))\) is product one-way. That is exactly c/0021, which the authors could not prove.

The second route. In the backdoored random oracle model of Bauer, Farshim and Mazaheri the leakage oracle is strong enough to implement Simon’s collision finder, and two independent instances combine into a collision-resistant hash function under a communication-complexity conjecture. This gives a helpful idealized primitive, not helpful one-way functions, so it does not settle the statement above.

What is actually proved. Two relaxations, both conditional on c/0021. Theorem 6.8 gives the distributional version, where reductions need only work for a measure-one set of implementations; Theorem 6.12 gives the class-reduction version in the sense of Shaltiel, where they need only work for efficient implementations, via a Borel–Cantelli argument over the countable class of efficient one-way functions.

The gap between separation and uselessness is known to be non-empty, but so far only for contrived reasons: the joint primitive consisting of a collision-resistant hash function and a trapdoor permutation is not implied by either component alone, yet each component is trivially helpful for it. A proof here would give what the paper calls “a natural (and important) example of a primitive which does not black-box imply another primitive, yet is black-box helpful for it”.

The reason the distributional relaxation does not upgrade to the full statement is worth stating precisely, because it is the whole difficulty: the measure-one set of auxiliary implementations depends on the one-way function, so no single universal \(\mathcal{Z}\) can be extracted. Restricting to efficient one-way functions is what recovers one, and that restriction is the content of the class-reduction relaxation rather than a technicality of its proof.

A solver should be clear which direction they are attacking. The conjecture and its negation are both strong unproved statements, and neither follows from the absence of progress on the other.

Prove or refute the conjecture: exhibit an auxiliary primitive \(\mathcal{Z}\) as above, or prove one-way functions are fully black-box useless for collision resistance.
Settle c/0021, which would upgrade both relaxations and is the paper’s own preferred route.
Decide whether the reconstruction of \(\mathcal{CRH}\) used here — keyed, generic compression — is neutral for the statement, as the drafter believes but did not verify.
Check the intervening literature on one-way product functions and on Simon’s oracle, which the drafter did not survey exhaustively.
Formalize the statement in Lean. Primitives, joint primitives and fully black-box reductions all need writing first.

Couteau, Farshim, and Mahmoody. Black-Box Uselessness: Composing Separations in Cryptography. Cryptology ePrint Archive, Report 2021/016. Conjecture 6.1 and its two relaxations (Theorems 6.8 and 6.12); the routes via Holmgren–Lombardi and via backdoored random oracles.
Simon. Finding collisions on a one-way street: can secure hash functions be based on general assumptions? EUROCRYPT 1998, LNCS 1403, pp. 334–345. The separation this statement composes.
Holmgren and Lombardi. Cryptographic hashing from strong one-way functions (or: one-way product functions and their applications). FOCS 2018, pp. 850–858. One-way product functions imply collision resistance.
Bauer, Farshim, and Mazaheri. Combiners for backdoored random oracles. CRYPTO 2018, Part II, LNCS 10992, pp. 272–302. The second route’s model.