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:
“There are theoretical reformers at all times, and all the world over, living on anticipation.”
—Henry David Thoreau (1817–1862)
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)