One-way function

A one-way function is a function which is easy to calculate but hard to invert — it is difficult to calculate the input to the function given its output. The precise meanings of "easy" and "hard" can be specified mathematically. With rare exceptions, almost the entire field of public key cryptography rests on the existence of one way functions.

Formally, a one-way function is a computable function f with the following properties:

• Computing f(x), given x, is tractable (i.e., f is computable by a polynomial-time algorithm; see complexity theory).
• Computing any preimage of f(x) (i.e., an element y such that f(y) = f(x)), given only f(x) for some random x, is not tractable (i.e. no probabilistic polynomial time algorithm exists).

It is not known whether one-way functions exist. In fact, their existence would imply P≠NP, resolving the foremost unsolved question of computer science. However, it is not clear if P≠NP implies the existence of one-way function. It is also not clear if the existence of one-way function implies the existence of one-to-one one-way function. However, it has been shown that P≠UP (a subclass of NP) implies the existence of one-to-one one-way functions; see UP for more.

It is known that the existence of one-way functions implies the existence of many other useful cryptographic primitives, including (but not limited to):

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

There are several (classes of) functions that are candidates for one way functions. Multiplication of two large primes is one such: this is because integer factorization is thought to be a hard problem. Another is exponentiation in certain groups: this one relies on the presumed hardness of the computing the discrete logarithm.

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.

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

References

• Goldreich, Oded (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the author's web site.