In mathematics, a negligible function is a
function
such that for every positive integer c there exists an integer Nc such that for all x > Nc,
![{\displaystyle |\mu (x)|<{\frac {1}{x^{c}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/73f8d816110dbbfe0695fee75f8a5d12891fc020)
Equivalently, we may also use the following definition.
A function
is negligible, if for every
positive polynomial poly(·) there exists an integer Npoly > 0 such that for all x > Npoly
![{\displaystyle |\mu (x)|<{\frac {1}{\operatorname {poly} (x)}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adcf2fc78073035903a0c3af5c56118947f86a81)
History
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 ![{\displaystyle |f(x)-f(x_{0})|<\varepsilon .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f9414e1a32256b8485dffecfee23300ecf2fe5d)
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 infinitesimal functions are a superset of negligible functions.
Use in cryptography
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
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
![[icon]](https://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png) | This section needs expansion. You can help by
adding to it. (March 2018) |
is negligible for any
.
is negligible.
is negligible.
is negligible.
is not negligible, for positive
.
Assume
, we take the limit as
:
Negligible:
![{\displaystyle f(n)=1/x^{n/2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0ce31bd683fa18ab6ffc03df8c938d4ba9c52e5)
for ![{\displaystyle k\geq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d30d7dcf305b7bce39d36df72fe3985b47aa9961)
for ![{\displaystyle k\geq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d30d7dcf305b7bce39d36df72fe3985b47aa9961)
![{\displaystyle f(n)=1/x^{\sqrt {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a771510d6c94aa6f3f4421e875f8e650cdca38c)
Non-negligible:
![{\displaystyle f(n)={\frac {1}{n^{\frac {1}{n}}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4da3a258dec2691462b6d5a233a93786d7cc4e33)
![{\displaystyle f(n)={\frac {1}{x^{n(\log {n})}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6d8296d64cdb604245e4eb18f81ad88aeca11c3)
See also
References