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)
“... 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)