One way function

A one way function is a function which is "easy" to calculate but "hard" to invert — i.e, it is "hard" to calculate the input to the function given its output. One way functions are useful in cryptography for public key encyption and digital signatures.

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

• The computation of is tractable (which generally means that a polynomial algorithm for the computation is known, see complexity theory).
• The computation of the preimage of (denoted ), on a random x, is not tractable (i.e. no polynomial time algorithm exists) given only .

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. 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 groupss: 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 cryptographic hash function is like a one way function except that it is not required to be bijective and has more stringent requirements for hardness of inversion.

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.