Negligible function (cryptography)

From Wikipedia, the free encyclopedia

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

Formally, \nu: \mathbb{N}{\rightarrow}\mathbb{R} is negligible if for any nonzero 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. The general outline of a cryptographic security statement is as follows: The probability that an adversary can "break the security of the scheme" is a negligible function of the security parameter (which measures the input size of the problem). Examples of "breaking the security of the scheme" might include distinguishing between encryptions of two different messages, recovering a key, etc.

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. For example, if an attack succeeds in violating a security condition only with negligible probability, and the attack is repeated a polynomial number of times, the success probability of the overall attack still remains negligible. 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.

[edit] See also

[edit] References

  1. ^ Oded Goldreich. Foundations of Cryptography, volume Basic Tools. Cambridge University Press, 2001.