Negligible function (cryptography)

From Wikipedia, the free encyclopedia

You have new messages (last change).

In cryptography, a negligible function is one that approaches zero faster than the reciprocal of any polynomial.

Formally, \nu: N \rightarrow R is negligible if for any polynomial p, there exists m such that \forall n > m, |\nu(n)| < \frac{1}{p(n)}.

Negligible functions are typically used to quantify the security of a cryptographic algorithm or protocol. For instance, one might say that the adversary's chance of recovering a key is a negligible function of the security parameter (which measures the input size of the problem).

The reciprocal-of-polynomial formulation is used for the same reason that computational boundedness is defined as polynomial running time: it has mathematical closure properties that make it tractable in the asymptotic setting. In practice one might want to have more concrete functions bounding the adversary's success probability and to choose the security parameter large enough that this probability is smaller than some threshold, say 2-128.

Functions that are not negligible are significant. Thus the statement that the adversary's chance of identifying the underlying distribution of a random variable is significantly greater than one half means that the difference between the probability in question and one half is not a negligible function of the security parameter.

Retrieved from "http://en.wikipedia.org../../../n/e/g/Negligible_function_%28cryptography%29.html"