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)
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)