# Negligible function

In mathematics, a **negligible function** is a function such that for every positive integer *c* there exists an integer *N*_{c} such that for all *x* > *N*_{c},

Equivalently, we may also use the following definition.
A function is **negligible**, if for every positive polynomial poly(·) there exists an integer *N*_{poly} > 0 such that for all *x* > *N*_{poly}

## History[edit]

The concept of *negligibility* can find its trace back to sound models of analysis. Though the concepts of "continuity" and "infinitesimal" became important in mathematics during Newton and Leibniz's time (1680s), they were not well-defined until the late 1810s. The first reasonably rigorous definition of *continuity* in mathematical analysis was due to Bernard Bolzano, who wrote in 1817 the modern definition of continuity. Later Cauchy, Weierstrass and Heine also defined as follows (with all numbers in the real number domain ):

**(Continuous function)**A function is*continuous*at if for every , there exists a positive number such that implies

This classic definition of continuity can be transformed into the
definition of negligibility in a few steps by changing parameters used in the definition. First, in the case with , we must define the concept of "*infinitesimal function*":

**(Infinitesimal)**A continuous function is*infinitesimal*(as goes to infinity) if for every there exists such that for all^{[citation needed]}

Next, we replace by the functions where or by where is a positive polynomial. This leads to the definitions of negligible functions given at the top of this article. Since the constants can be expressed as with a constant polynomial this shows that negligible functions are a subset of the infinitesimal functions.

## Use in cryptography[edit]

In complexity-based modern cryptography, a security scheme is
*provably secure* if the probability of security failure (e.g.,
inverting a one-way function, distinguishing cryptographically strong pseudorandom bits from truly random bits) is **negligible** in terms of the input = cryptographic key length . Hence comes the definition at the top of the page because key length must be a natural number.

Nevertheless, the general notion of negligibility doesn't require that the input parameter is the key length . Indeed, can be any predetermined system metric and corresponding mathematical analysis would illustrate some hidden analytical behaviors of the system.

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 (see #Closure properties). 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}.

## Closure properties[edit]

One of the reasons that negligible functions are used in foundations of complexity-theoretic cryptography is that they obey closure properties.^{[1]} Specifically,

- If are negligible, then the function is negligible.
- If is negligible and is any real polynomial, then the function is negligible.

Conversely, if is not negligible, then neither is for any real polynomial .

## Examples[edit]

- is negligible for any .
- is negligible.

## See also[edit]

- Negligible set
- Colombeau algebra
- Nonstandard numbers
- Gromov's theorem on groups of polynomial growth
- Non-standard calculus

## References[edit]

**^**Katz, Johnathan.*Introduction to modern cryptography*. Lindell, Yehuda (Second ed.). Boca Raton. ISBN 9781466570269. OCLC 893721520.

- Goldreich, Oded (2001).
*Foundations of Cryptography: Volume 1, Basic Tools*. Cambridge University Press. ISBN 0-521-79172-3. - Sipser, Michael (1997). "Section 10.6.3: One-way functions".
*Introduction to the Theory of Computation*. PWS Publishing. pp. 374–376. ISBN 0-534-94728-X. - Papadimitriou, Christos (1993). "Section 12.1: One-way functions".
*Computational Complexity*(1st ed.). Addison Wesley. pp. 279–298. ISBN 0-201-53082-1. - Colombeau, Jean François (1984).
*New Generalized Functions and Multiplication of Distributions*. Mathematics Studies 84, North Holland. ISBN 0-444-86830-5. - Bellare, Mihir (1997). "A Note on Negligible Functions". Dept. of Computer Science & Engineering University of California at San Diego. CiteSeerX 10.1.1.43.7900.