|
==Theoretical definition==
A function ''f'' : {0, 1}<sup>*</sup> → {0, 1}<sup>*</sup> is '''one-way''' if ''f'' can be computed by a polynomial -time algorithm, but any polynomial -time [[randomized algorithm]] <math>F</math> that attempts to compute a pseudo-inverse for ''f'' succeeds with [[Negligible function|negligible]] probability. (The * superscript means any number of repetitions, ''see'' [[Kleene star]].) That is, for all randomized algorithms <math>F</math> , all positive integers ''c'' and all sufficiently large ''n'' = length(''x'') ,
: <math>\Pr[f(F(f(x))) = f(x)] < n^{-c},</math>
where the probability is over the choice of ''x'' from the [[Uniform distribution (discrete)|discrete uniform distribution]] on {0, 1}<sup>''n''</sup>, and the randomness of <math>F</math>.<ref>Many authors view this definition as strong one-way function. A weak one-way function can be defined similarly except that the probability that every adversarial <math>F</math> fails to invert ''f'' is noticeable. However, one may construct strong one-way functions based on weak ones. Loosely speaking, strong and weak versions of one-way function are equivalent theoretically. See Goldreich's Foundations of Cryptography, vol. 1, ch . 2.1–2.3.</ref>
Note that, by this definition, the function must be "hard to invert" in the [[best, worst and average case|average-case, rather than worst-case]] sense. This is different from much of complexity theory (e.g., [[NP-hard]]ness), where the term "hard" is meant in the worst-case. That is why even if some candidates for one-way functions (described below) are known to be [[NP-complete]], it does not imply their one-wayness. The latter property is only based on the lack of known algorithms to solve the problem.
It is not sufficient to make a function "lossy" (not one-to-one) to have a one-way function. In particular, the function that outputs the string of ''n'' zeros on any input of length ''n'' is ''not'' a one-way function because it is easy to come up with an input that will result in the same output. More precisely: For such a function that simply outputs a string of zeroes, an algorithm ''F'' that just outputs any string of length ''n'' on input ''f''(''x'') will "find" a proper preimage of the output, even if it is not the input which was originally used to find the output string.
==Related concepts==
|
