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 desire to serve the common good must without fail be a requisite of the soul, a necessity for personal happiness; if it issues not from there, but from theoretical or other considerations, it is not at all the same thing.”
—Anton Pavlovich Chekhov (1860–1904)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)