Related concepts[edit]
A one-way permutation is a one-way function that is also a permutation—that is, a one-way function that is bijective. One-way permutations are an important cryptographic primitive, and it is not known if their existence is implied by the existence of one-way functions.
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.
A collision-free hash function f is a one-way function that is also collision-resistant; that is, no randomized polynomial time algorithm can find a collision—distinct values x, y such that f(x) = f(y)—with non-negligible probability.[4]
If f is a one-way function, then the inversion of f would be a problem whose output is hard to compute (by definition) but easy to check (just by computing f on it). Thus, the existence of a one-way function implies that FP ≠ FNP, which in turn implies that P ≠ NP. However, P ≠ NP does not imply the existence of one-way functions.
The existence of a one-way function implies the existence of many other useful concepts, including:
Universal one-way function[edit]
There is an explicit function f that has been proved to be one-way, if and only if one-way functions exist.[5] In other words, if any function is one-way, then so is f. Since this function was the first combinatorial complete one-way function to be demonstrated, it is known as the "universal one-way function". The problem of finding a one-way function is thus reduced to proving—perhaps non-constructively—that one such function exists.