Existence of one-way permutations

A function $\mu\colon\mathbb N\to[0,1]$ is negligible if for every $c>0$ there is $N$ with $\mu(n)\le n^{-c}$ for all $n\ge N$. A probabilistic polynomial-time (PPT) algorithm is a randomized Turing machine whose running time is bounded by a fixed polynomial in its input length.

A function $f\colon\{0,1\}^*\to\{0,1\}^*$ is a one-way permutation if it satisfies the following three conditions.

1. Permutation. For every $n\ge1$, the restriction $f_n=f|_{\{0,1\}^n}$ is a bijection $\{0,1\}^n\to\{0,1\}^n$.
2. Easy to compute. A single deterministic algorithm computes $f(x)$ in time polynomial in $|x|$.
3. Hard to invert. For every PPT algorithm $A$ the function

$$\varepsilon_A(n)=\Pr_{x\leftarrow\{0,1\}^n}\bigl[A(1^n,f(x))=x\bigr]$$

is negligible. The probability is over the uniform choice of $x$ and the coins of $A$.

This is the standard definition with uniform adversaries [3, 11]. The domain of $f_n$ is all of $\{0,1\}^n$, and there is no key or index chosen by a sampling algorithm. In the non-uniform variant, $A$ ranges over families of polynomial-size circuits; existence there is also open.

Problem. Prove or disprove that one-way permutations exist.

A one-way permutation is in particular a one-way function, so a proof of existence would also prove that one-way functions exist. It would also separate complexity classes. The language $\{(y,i,b): \text{the } i\text{-th bit of } f^{-1}(y) \text{ is } b\}$ lies in $\mathsf{UP}\cap\mathsf{coUP}$, because each $y$ has exactly one preimage. If this language were in $\mathsf{BPP}$, $f$ could be inverted everywhere with high probability. Hence one-way permutations imply $\mathsf{UP}\cap\mathsf{coUP}\not\subseteq\mathsf{BPP}$, and in particular $\mathsf P\neq\mathsf{NP}$.

Background

One-way permutations give the simplest constructions of many primitives. Blum and Micali, and Yao, built pseudorandom generators by iterating a one-way permutation and outputting a hard-core bit at each step [1, 2]. Goldreich and Levin showed that every one-way function has a hard-core predicate [4]. With a permutation, the generator is then immediate. From general one-way functions the analogous construction is much harder [5].

Most proposed candidates are keyed collections rather than single full-domain permutations. Examples are modular exponentiation $x\mapsto g^x \bmod p$ and the RSA function, where a key such as $(p,g)$ or $(N,e)$ is sampled first. Each such permutation acts on a domain that depends on the key. Candidates of the keyless, full-domain kind asked for here are scarce [8].