One-way function

''Do one-way functions exist?''

A one-way function is a function that is easy to compute but hard to invert — given the output of the function it is difficult to find any input which yields this output. The precise meanings of "easy" and "hard" can be specified mathematically:

"Easy" means that some algorithm can compute the function in probabilistic polynomial time (in the input size). "Hard" means no such probabilistic polynomial-time algorithm exists. However, unlike hardness such as NP-hardness, "hard" in the context of one-way functions refers to the average case. Hardness on average is typically proven via random self-reducibility.

Existence of one-way functions

The existence of one-way functions is an open conjecture. In fact, their existence would imply P≠NP, resolving the foremost unsolved question of computer science. However, it is not known whether P≠NP implies the existence of one-way functions, mainly because of the worst-case hardness vs. average-case hardness distinction.

The existence of some one-way functions implies the existence of many other useful cryptographic primitives, including:

• Pseudorandom number generators;
• Pseudorandom function families;
• Bit commitment schemes;
• Digital signature schemes (secure against adaptive chosen-message attack).

A trapdoor one-way function or trapdoor permutation is a special kind of one-way function. Such a function is hard to invert unless some secret information, called the trapdoor, is known. RSA is a well known example of a function believed to belong to this class. For example, it's believed to be difficult to factorize a product of two primes, but it is easy as soon as you know one of them.

A distinct but related concept in cryptography is that of the cryptographic hash function.

Candidates for one-way functions

Following are several candidates for one-way functions. Clearly, it is not known whether these functions are indeed one-way. This is only a conjecture supported by extensive research which has so far failed to produce an efficient inverting algorithm.

Integer factorization

In spite of the extensive research directed towards the construction of the efficient (integer) factoring algorithm, the best algorithms known for factoring an integer N run in time . Hence it is reasonable to believe that the function which multiplies a pair of integers (represented as bitstrings) is one-way.

Rabin (quadratic residue) function

It can be shown that extracting square roots modulo N is computationally equivalent to factoring N (i.e., the two tasks are reducible to one another via probabilistic polynomial-time reductions). Hence, squaring modulo a composite is a one-way function if and only if factoring is intractable. The Rabin cryptosystem is based on the assumption that Rabin function is one-way (see also quadratic residue).

Discrete logarithms

Another computational number problem which is widely believed to be intractable is that of extracting discrete logarithms in a finite field (and in particular of prime cardinality). Thus exponentiation in the finite field is a reasonable candidate for one-way function. The ElGamal encryption scheme is based on this.

Other candidates

Other candidates for one-way functions have been based on the hardness of the decoding of random linear codes, the subset sum problem, or other NP-complete problems.