In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one-to-one is not considered sufficient of a function for it to be called one-way (see Theoretical Definition, below).
The existence of such one-way functions is still an open conjecture. In fact, their existence would prove that the complexity classes P and NP are not equal, thus resolving the foremost unsolved question of theoretical computer science. Existence of a proof that P and NP are not equal would not directly imply the existence of one-way functions.
In applied contexts, the terms "easy" and "hard" are usually interpreted relative to some specific computing entity; typically "cheap enough for the legitimate users" and "prohibitively expensive for any malicious agents". One-way functions, in this sense, are fundamental tools for cryptography, personal identification, authentication, and other data security applications. While the existence of one-way functions in this sense is also an open conjecture, there are several candidates that have withstood decades of intense scrutiny. Some of them are essential ingredients of most telecommunications, e-commerce, and e-banking systems around the world.
Read more about One-way Function: Theoretical Definition, Related Concepts, Theoretical Implications of One-way Functions, Candidates For One-way Functions, Universal One-way Function
Famous quotes containing the word function:
“The mothers and fathers attitudes toward the child correspond to the childs own needs.... Mother has the function of making him secure in life, father has the function of teaching him, guiding him to cope with those problems with which the particular society the child has been born into confronts him.”
—Erich Fromm (19001980)