Black-box uselessness: when a primitive cannot even help

A separation says X does not build Y on its own. Uselessness says X never helps anyone else build Y either.

Motivation

A black-box separation says that primitive \(X\) does not yield primitive \(Y\). It says nothing about \(X\) used alongside something else, and that is the case protocol designers are actually in: nobody builds key agreement from a one-way function alone, they build it from a one-way function together with whatever else is lying around. Couteau, Farshim and Mahmoody ask the composed question. Call \(X\) black-box useless for \(Y\) if for every auxiliary primitive \(Z\), a black-box construction of \(Y\) from the pair \((X, Z)\) implies there was already one from \(Z\) alone — \(X\) contributed nothing. Call it black-box helpful otherwise, meaning some \(Z\) exists that is insufficient by itself and sufficient once \(X\) is added.

Uselessness is strictly stronger than separation and is the property a composed statement needs. Helpfulness is its negation, and exhibiting a helpful primitive means exhibiting a genuine inhabitant of the gap between “does not imply” and “does not help” — which is where an unexpected future construction would have to live.

The interesting fact is that the two known answers point in opposite directions. For key agreement the paper conjectures that one-way functions are useless, and proves it for three restricted protocol classes. For collision resistance the same authors conjecture the opposite, that one-way functions are helpful, because the separation there is Simon’s oracle argument and it is not clear how to relativize it. Both conjectures are open, and the second reduces to a hardness question about Simon’s oracle that is open in its own right.

Provenance and history

All three statements in this hub come from one paper: Geoffroy Couteau, Pooya Farshim and Mohammad Mahmoody, Black-Box Uselessness: Composing Separations in Cryptography, Cryptology ePrint Archive Report 2021/016, which introduces the uselessness framework and leaves each of these open in its own voice. Bibliographic details verified against ePrint on 18 August 2026.

The statements were drafted by scripts/harvest_conjectures.py from the paper’s PDF, each with a provenance file recording the quotes it grounded and an adversarial check of its own output; the corrections those checks asked for were applied before the statements were published here. Nothing in this hub has been reviewed by a human, which is what the status badges on each page say.

Two of the harvested drafts — simon-oracle-amplification and simon-oracle-simultaneous-inversion — turned out to be the same object, the paper’s Conjecture 6.7, written up twice with different framing. They are published here as one statement, c/0021, which is why this hub holds three statements and not four.

Parameter lattice

Two axes: the target primitive, and which way the paper conjectures the answer falls.

target conjectured tracked settled fragments
key agreement useless c/0020 three restricted protocol classes (Theorems 4.1, 4.9, 4.12)
collision-resistant hashing helpful c/0019 two relaxations, both conditional on c/0021
the hardness question underneath — c/0021 known only without the collision finder, and only when the one-way function is a random oracle

The paper settles neither headline cell. What it settles are fragments: restricted protocol classes on the uselessness side, and conditional relaxations on the helpfulness side. The third row is not a uselessness question at all — it is the product-hardness statement the helpfulness route runs through, and both of the relaxations the paper proves take it as a hypothesis.

Statements in this hub