Theoretical Definition
A function f: {0, 1}* → {0, 1}* is one-way if f can be computed by a polynomial time algorithm, but for every randomized algorithm A which runs in time polynomial in |x|, every polynomial p(n), and all sufficiently large n
where the probability is over the choice of x from the uniform distribution on {0, 1}n, and the randomness of A.
Note that, by this definition, the function must be "hard to invert" in the average-case, rather than worst-case sense. This is different from much of complexity theory (e.g., NP-hardness), where the term "hard" is meant in the worst-case.
It is not sufficient to make a function "lossy" (not one-to-one) to have a one-way function. In particular, the function which outputs the string of n zeros on any input of length n is not a one-way function. The reason is that an algorithm A which just outputs any string of length n on input f(x) does find a proper preimage of the output, even if it is not the input which was originally used to find the output string.
Read more about this topic: One-way Function
Famous quotes containing the words theoretical and/or definition:
“The hypothesis I wish to advance is that ... the language of morality is in ... grave disorder.... What we possess, if this is true, are the fragments of a conceptual scheme, parts of which now lack those contexts from which their significance derived. We possess indeed simulacra of morality, we continue to use many of the key expressions. But we have—very largely if not entirely—lost our comprehension, both theoretical and practical, of morality.”
—Alasdair Chalmers MacIntyre (b. 1929)
“The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)