Content deleted Content added
m →Theoretical implications of one-way functions: punct., fmt. |
→Theoretical definition: Added non-breaking space Tags: Mobile edit Mobile web edit Advanced mobile edit |
||
Line 12:
: <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.
| |||