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. 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 <math>f(x)<math> is tractable (which generally means that a polynomial algorithm for the computation is known, see complexity theory).
- The computation of the preimage of <math>f(x)<math> (denoted <math>f^{-1}(x)<math>), on a random x, is not tractable (i.e. no polynomial time algorithm exists) given only <math>f(x)<math>.
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 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 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 .
