Existence of one-way functions

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 function if it satisfies the following two conditions.

1. Easy to compute. A deterministic algorithm computes $f(x)$ in time polynomial in $|x|$.
2. Hard to invert. For every PPT algorithm $A$ the function

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

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

The adversary only has to find some preimage of $f(x)$, not $x$ itself. This is the standard definition with uniform adversaries [3, 12]. In the non-uniform variant, $A$ ranges over families of polynomial-size circuits. Non-uniform one-way functions are also one-way in the uniform sense, and their existence is also open.

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

If one-way functions exist, then $\mathsf{NP}\not\subseteq\mathsf{BPP}$, and in particular $\mathsf P\neq\mathsf{NP}$. Indeed, the language $\{(1^n,y,w): \exists z\in\{0,1\}^n,\ z \text{ extends } w,\ f(z)=y\}$ is in $\mathsf{NP}$. A $\mathsf{BPP}$ algorithm for it would find preimages bit by bit with high probability. So a proof of existence must in particular prove $\mathsf P\neq\mathsf{NP}$. A disproof would show that every efficiently computable function can be inverted on a non-negligible fraction of inputs.

Background

Diffie and Hellman introduced one-way functions as the basis for public-key cryptography in 1976 [1]. Yao gave the modern definitions and showed that weak one-way functions, which are hard to invert only on a $1/\mathrm{poly}(n)$ fraction of inputs, can be converted into one-way functions in the sense above [2].

One-way functions are the minimal assumption of complexity-based cryptography. Their existence is equivalent to the existence of pseudorandom generators [5], pseudorandom functions [6], and digital signatures [7]. Impagliazzo and Luby showed that private-key encryption and many other cryptographic tasks require one-way functions [4]. Levin constructed an explicit function that is one-way if any one-way function exists [8]. Impagliazzo's "five worlds" survey places the problem among related questions in average-case complexity [9].