Product Hardness of a One-Way Function and a Random Permutation Given a Collision Finder

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

Inverting a random permutation costs \(2^{\lambda}\), and Simon showed that this survives handing the adversary a collision finder for circuits built from the permutation. This conjecture asks for the product version: give an adversary both a one-way function’s image and a random permutation’s image, plus the collision finder, and it should not invert both at once with probability better than the product of the two individual bounds. It is the hardness statement the route to one-way functions being helpful for collision resistance runs through, and the paper leaves it open as a question of possible independent interest.

View PDF · Download LaTeX source

Let \(\mathsf{RP} = \{\mathsf{RP}_{\lambda}\}\) be a random permutation and \(\mathsf{Coll}^{\mathsf{RP}}\) Simon’s collision finder, which on an oracle circuit with \(\mathsf{RP}\)-gates and recursive \(\mathsf{Coll}\)-gates returns a uniformly random collision for it.

Let \(\varepsilon: \mathbb{N} \to (0,1]\) be any function, and let \(\mathsf{F}\) be an oracle implementing an \(\varepsilon\)-secure one-way function: for every oracle-aided PPT machine \(B\) and all sufficiently large \(\lambda\), \[\Pr_{x \gets \{0,1\}^{\lambda}}\left[B^{\mathsf{F}}(1^{\lambda}, \mathsf{F}(x)) \in \mathsf{F}^{-1}(\mathsf{F}(x))\right] \le \varepsilon(\lambda).\]

Conjecture. For every oracle-aided PPT machine \(A\) there exists a polynomial \(\mathrm{poly}\) such that, for a measure-one set of random permutations \(\mathsf{RP}\) and collision finders \(\mathsf{Coll}^{\mathsf{RP}}\), and for all sufficiently large \(\lambda\), \[\Pr\left[(x_1, x_2) = A^{\mathsf{F}, \mathsf{RP}, \mathsf{Coll}^{\mathsf{RP}}}\bigl(\mathsf{F}(x_1), \mathsf{RP}(x_2)\bigr)\right] \le \varepsilon(\lambda) \cdot \frac{\mathrm{poly}(\lambda)}{2^{\lambda}},\] the probability being over \((x_1, x_2) \gets (\{0,1\}^{\lambda})^{2}\) and the coins of \(A\).

This is the paper’s Conjecture 6.7, the strong version. Its Conjecture 6.6 is the same statement with the collision finder dropped, and is weaker.

One quantifier a reviewer should check. The paper’s inline \(\mathrm{poly}(\lambda)\) does not make it unambiguous whether the polynomial is chosen before or after the measure-one set of oracles. The transcription above fixes it as \(\exists\,\mathrm{poly}\) preceding the measure-one quantifier, which is the reading the drafter took.

Open, and open in the generality that matters here.

What is known. Impagliazzo and Rudich give the single-oracle bound: for any attacker, with measure one over the choice of \(\mathsf{RP}\), the permutation cannot be inverted with probability better than \(\mathrm{poly}(\lambda)/2^{\lambda}\). Simon extends this to the presence of the collision finder — which is exactly what separates collision-resistant hashing from one-way permutations, since \(\mathsf{Coll}\) trivially breaks collision resistance. Both extend to a setting with an auxiliary oracle independent of \((\mathsf{RP}, \mathsf{Coll})\).

What is missing is the product. Of the weak version — no collision finder — the paper records only that it “is known in the case where \(F\) is itself a random oracle, but not when it is an arbitrary one-way function”. The strong version, with the collision finder, is not claimed to be known in any case. This distinction is easy to lose: a “known” attached to Conjecture 6.6 does not transfer to Conjecture 6.7.

A warm-up the paper suggests. Replace the arbitrary one-way function by an \(\varepsilon\)-secure one-way permutation and the pair \((\mathsf{RP}, \mathsf{Coll})\) by a random oracle, and ask whether an attacker can invert both simultaneously with probability better than \(\mathrm{negl}(n)/2^{n}\).

What it buys. Theorem 6.8 shows this conjecture implies that one-way functions are distributionally fully black-box helpful for collision-resistant hashing; Theorem 6.12 shows it implies the class-reduction relaxation. Both are relaxations of c/0019 rather than that statement itself — the distributional route cannot produce a universal auxiliary primitive, because the measure-one set of implementations depends on the one-way function.

The appeal of the statement is that it looks like it should follow from independence. \(\mathsf{RP}\) is drawn independently of \(\mathsf{F}\), so the intuition is that an adversary has nothing better to do than attack the two separately, and the product bound is what “separately” means. The reason that is not a proof is the collision finder: \(\mathsf{Coll}^{\mathsf{RP}}\) answers queries about circuits that may embed \(\mathsf{F}\)-gates, so the two oracles are not independent from the adversary’s point of view even though they are as objects.

Via Holmgren and Lombardi, exponentially secure one-way product functions black-box imply collision-resistant hashing, which is why a product-hardness statement is what the helpfulness route needs rather than a merely joint one.

This page is the merge of two harvested drafts. simon-oracle-amplification and simon-oracle-simultaneous-inversion were both written from the same page of the same paper and state the same conjecture, differing only in framing and in the surrounding exposition. Publishing them as two statements would have spent two identifiers on one object. The LaTeX here is the first; the second stays in latex/conjectures/ and is not separately promoted.

Prove or refute the conjecture as stated, with the collision finder present and an arbitrary \(\varepsilon\)-secure one-way function.
Settle the weak version (Conjecture 6.6, no collision finder) for an arbitrary one-way function, which is open too and is the natural first target.
Settle the paper’s warm-up: one-way permutation plus random oracle, simultaneous inversion.
Fix the quantifier order against the authors’ intent — whether the polynomial precedes or follows the measure-one quantifier.
Formalize the statement in Lean. The collision-finder oracle and measure-one-over-oracles quantification both need writing first.

Couteau, Farshim, and Mahmoody. Black-Box Uselessness: Composing Separations in Cryptography. Cryptology ePrint Archive, Report 2021/016. Conjecture 6.7 (strong version) and Conjecture 6.6 (weak); Theorems 6.8 and 6.12; the warm-up in footnote 9.
Impagliazzo and Rudich. Limits on the provable consequences of one-way permutations. STOC 1989, pp. 44–61. The single-oracle inversion bound.
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 collision finder, and the bound surviving it.
Holmgren and Lombardi. Cryptographic hashing from strong one-way functions (or: one-way product functions and their applications). FOCS 2018, pp. 850–858. Why product hardness is the right target.