Relationship between existence of OWFs and OWPs

Question

OWPs are bijective OWFs, so every OWP is a OWF, but not the other way around.

However, I'm wondering what the relationship between the existence of both types of functions is. Obviously if one assumes OWPs to exist, OWFs will also exist.

But: Does the existence of OWFs imply the existence of OWPs?

Answer 1

Short answer: "No".

The standard way to establish a statement of the form if a primitive $B$ exists then another primitive $A$ also exists is through a black-box reduction. This involves two steps:

1. Constructing an instance $\alpha$ of $A$ given black-box access to an instance $\beta$ of $B$ --- this is denoted by $\alpha^\beta$, where $\beta$ in the superscript refers to $\alpha$ having only oracle-access to $\beta$; and
2. Showing that $\alpha^\beta$ is hard to break assuming $\beta$ is --- this, in turn, is accomplished through a reduction algorithm $\mathcal{B}$ that breaks $\beta$ given an adversary $\mathcal{A}$ that breaks $\alpha$. ($\mathcal{B}$ only has black-box access to $\mathcal{A}$.)

Primitive $A$ is said to be black-box-reduced to primitive $B$. (Henceforth, by reduced, we mean black-box-reduced.)

Rudich showed$^*$ in his PhD thesis that one-way permutations ($OWPs$) cannot be reduced to one-way functions ($OWFs$) --- i.e., given a $OWF$ $f$, one cannot construct a $OWP$ $\pi$ in the manner described above. In particular, what he showed is that Step 2 is not possible: i.e., there cannot exist a reduction algorithm $\mathcal{B}$ that breaks $f$ given an adversary $\mathcal{A}$ that breaks $\pi^f$.

Note that the above is a very strong statement: we are ruling out all reduction algorithms $\mathcal{B}$. One way to do this is through an "oracle separation". What Rudich showed is that there exists an oracle $\mathcal{O}$ relative to which $OWFs$ exist, but any construction of OWP $\pi$ that uses $\mathcal{O}$ can be broken using an algorithm $\mathcal{A}^*$ that makes only a "few" (polynomially-many) queries to $\mathcal{O}$. The oracle $\mathcal{O}$ was chosen by Rudich as the random oracle, which is one-way with high probability -- in particular, it takes any algorithm "many" (nearly exponential) queries to a random oracle to invert it. The workings of $\mathcal{A}^*$ is a bit involved, but the high-level idea is it iteratively queries $\mathcal{O}$ on a "few" points in such a manner that it learns something new in every iteration. Since the implementation of $\pi$ is efficient, $\mathcal{A}^*$ can successfully invert $\pi$ using only a polynomial queries to $\mathcal{O}$. Note that $\mathcal{A}^*$ is only query-efficient, and runs in polynomial time only if it has access to a $\mathsf{PSPACE}$ oracle. But there is no way reduction $B$ could break the OWF ($\mathcal{O}$, i.e.) using $\mathcal{A}^*$ as the latter makes only a few queries to $\mathcal{O}$.

Matsuda and Matsuura strengthened the above result to show that a $OWP$ cannot be reduced even to injective $OWFs$ (arguably the closest primitive to $OWPs$). §1.2 in that paper contains a more detailed (although still intuitive) explanation of the Rudich separation .

P.S. Oracle separations have been used extensively in cryptography. Some other examples are:

1. Public-key cryptography cannot be based on OWFs: Impagliazzo and Rudich
2. Collision-resistant hash functions also cannot be based on OWFs: Simon

Other ways to rule out reductions are the so-called "meta-reduction" technique and the two-oracle technique. Fischlin has a nice exposition on these techniques: that should be a good starting point for further reading. You can read more about black-box reductions in this paper by Trevisan, Reingold and Vadhan.

$^*$Rudich's result was modulo a conjecture, which was proved later by Kahn et al..