one-way function

Informally, a function $f(x)$ is a one-way function if it is easy to compute but hard to invert.Or more generally, hard to pseudo-invert, i.e. to find any equivalent input $x'$ such that $f(x') = f(x)$.

A (strong) one-way function is one where any polynomial-time adversaryFormally, a 'non-uniform probabilistic polynomial time' adversary, where 'non-uniform' means we allow a family of adversaries whose description length can increase with the length of the input, rather than being a fixed Turing machine. has a negligible probability of returning a valid $x'$ such that $f(x) = f(x')$. Here the probability is over the randomness of the adversary and over a uniform distribution on inputs $x$, so this requires average-case hardness, rather than the worst-case hardness often used in complexity theory.

One-way functions are an essential primitive throughout cryptography. However, it is not rigorously established that any such functions actually exist. For example, one-way functions are trivially impossible if P=NP, so establishing their existence would depend at minimum on proving P != NP.

Weak one-way functions and hardness amplification

A weak one-way function is one where any polynomial-time adversary has a non-negligible probability of failing to return a valid $x'$ for random input $x$. Such a function can be invertible 'most of the time' but must be hard to invert in at least some cases.

For example, the multiplication function $f(x, y) = xy$ is thought to be hard to invert in general, but there are clearly many inputs where it's easy to invert: for example, the trivial adversary $A(z) = (2, \lfloor z/2 \rfloor)$ succeeds whenever $z$ is even, which happens with 50% probability.

Luckily it turns out that the existence of weak one-way functions implies that of strong one-way functions. Given a weak one-way function $f(x)$, we can simply run it on many inputs, constructing a new function

One can show that $f'$ is a strong one-way function, since to invert it on random input one would have to succeed $m$ times at inverting $f$, but since each such attempt has a non-negligible chance of failure, we can drive the chance of success to be exponentially small by choosing sufficiently large $m$.

Hard-core predicates

Note that even a strong one-way function can still leak significant information about the input. For example, given any strong one-way function $f$, the function $f'(x, y) = (f(x), y)$ is also a strong one-way function, but leaks half of the input $y$ in the clear. This illustrates that it's useful to be able to speak about functions of the input that cannot be easily recovered.

A hard-core bit $h(x) \in \{0, 1\}$ is a function of the input whose value can be guessed from $f(x)$ only with probability negligibly larger than $1/2$.

One can construct trivial cases; for example, if the one-way function simply ignores part of its input ($f(a, b) = f(a)$), then of course that part of the input will be unrecoverable by any adversary. Generally we care about non-trivial hard-core bits, such the bit is information-theoretically recoverable from the function output,

but not computationally feasible to recover.

It turns out that given any one-way function $f(x): \{0, 1\}^n \to \{0, 1\}^n$, we can construct a one-way function $g(x, r): \{0, 1\}^{2n}\to \{0, 1\}^{2n}$ with a hard-core bit $h(x, r): \{0, 1\}^{2n}\to \{0, 1\}$:

This is the Goldreich-Levin theorem. It's easy to see that if an adversary could perfectly invert $h$ from $g$, they could use this to invert $f$, simply reading off bits of $x$ by seeing if $h$ changes when they flip the corresponding bit in $r$. But by the assumption that $f$ is one-way, no such adversary can exist. The theorem is just an extension of this argument to cover the general case where the adversary can predict $h$ with probability non-negligibly better than chance, rather than perfectly.