Tag Info

A one-way function is a function which is easy to compute but hard to invert: given the output $f(x)$ of the function for some randomly chosen unknown input $x$, it should not be feasible to find an input $y$ (which may or may not equal $x$) such that $f(y) = f(x)$.

Formally, a function $f: \{0,1\}^* \to \{0,1\}^*$ is one-way if it can be computed by a polynomial-time algorithm, and if, for every polynomial-time randomized algorithm $A$, every polynomial $p$ and all sufficiently large $n$,

$$\mathrm{Pr}[\; f(A(f(x))) = f(x) \mid x \in \lbrace 0,1 \rbrace^n \;] < \frac{1}{p(n)}$$

i.e. the probability the any algorithm $A$ can find a preimage for $f(x)$, where $x$ is a string of length $n$, tends to zero faster than the reciprocal of any polynomial $p$.

No functions have been proven to be one-way, and indeed even the existence of one-way functions is an open problem. However, there do exist so-called "universal one-way functions", which are known to be one-way if one-way functions exist at all.

If one-way functions do exist, this implies the existence of various useful cryptographic tools, including pseudorandom generators, pseudorandom function families, commitment schemes, message authentication codes, digital signatures and IND-CCA2 secure encryption schemes. It would also imply a positive answer to the open problem of whether P ≠ NP.

Despite the lack of any existence proof, various functions are commonly believed to be likely to be one-way (and these functions underlie much of modern cryptography). Some examples include the multiplication of large primes, modular exponentiation and various cryptographic hash functions.

Closely related to one-way functions are so-called trapdoor one-way functions, which are easy to compute but hard to invert unless one knows a secret key used to construct the function. (Obviously, constructing the function from the key must itself be a one-way process as defined above.) Trapdoor one-way functions are the foundation of public-key cryptography.