In mathematics, a negligible function is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
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
In mathematics, a positive polynomial on a particular set is a polynomial whose values are positive on that set.
Let ''p'' be a polynomial in ''n'' variables with real coefficients and let ''S'' be a subset of the ''n''-dimensional Euclidean ...
poly(·) there exists an integer ''N''
poly > 0 such that for all ''x'' > ''N''
poly
:
History
The concept of ''negligibility'' can find its trace back to sound models of analysis. Though the concepts of "
continuity" and "
infinitesimal
In mathematics, an infinitesimal number is a quantity that is closer to zero than any standard real number, but that is not zero. The word ''infinitesimal'' comes from a 17th-century Modern Latin coinage ''infinitesimus'', which originally referr ...
" became important in mathematics during
Newton
Newton most commonly refers to:
* Isaac Newton (1642–1726/1727), English scientist
* Newton (unit), SI unit of force named after Isaac Newton
Newton may also refer to:
Arts and entertainment
* ''Newton'' (film), a 2017 Indian film
* Newton ( ...
and
Leibniz
Gottfried Wilhelm (von) Leibniz . ( – 14 November 1716) was a German polymath active as a mathematician, philosopher, scientist and diplomat. He is one of the most prominent figures in both the history of philosophy and the history of ma ...
's time (1680s), they were not well-defined until the late 1810s. The first reasonably rigorous definition of ''continuity'' in
mathematical analysis
Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, measure (mathematics), measure, infinite sequences, series (m ...
was due to
Bernard Bolzano
Bernard Bolzano (, ; ; ; born Bernardus Placidus Johann Gonzal Nepomuk Bolzano; 5 October 1781 – 18 December 1848) was a Bohemian mathematician, logician, philosopher, theologian and Catholic priest of Italian extraction, also known for his liber ...
, who wrote in 1817 the modern definition of continuity. Later
Cauchy
Baron Augustin-Louis Cauchy (, ; ; 21 August 178923 May 1857) was a French mathematician, engineer, and physicist who made pioneering contributions to several branches of mathematics, including mathematical analysis and continuum mechanics. He w ...
,
Weierstrass
Karl Theodor Wilhelm Weierstrass (german: link=no, Weierstraß ; 31 October 1815 – 19 February 1897) was a German mathematician often cited as the "father of modern mathematical analysis, analysis". Despite leaving university without a degree, ...
and
Heine also defined as follows (with all numbers in the real number domain
):
:(
Continuous function
In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value ...
) 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
In mathematics, an infinitesimal number is a quantity that is closer to zero than any standard real number, but that is not zero. The word ''infinitesimal'' comes from a 17th-century Modern Latin coinage ''infinitesimus'', which originally referr ...
) A continuous function
is ''infinitesimal'' (as
goes to infinity) if for every
there exists
such that for all
::
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
In complexity-based modern
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, a security scheme is
''
provably secure
Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields.
Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabiliti ...
'' if the probability of security failure (e.g.,
inverting a
one-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, s ...
, 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
In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...
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
Concrete is a composite material composed of fine and coarse aggregate bonded together with a fluid cement (cement paste) that hardens (cures) over time. Concrete is the second-most-used substance in the world after water, and is the most wi ...
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.
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
*
is negligible for any
.
*
is negligible.
*
is negligible.
*
is negligible.
*
is not negligible, for positive
.
See also
*
Negligible set
In mathematics, a negligible set is a set that is small enough that it can be ignored for some purpose.
As common examples, finite sets can be ignored when studying the limit of a sequence, and null sets can be ignored when studying the integr ...
*
Colombeau algebra
*
Nonstandard numbers
*
Gromov's theorem on groups of polynomial growth In geometric group theory, Gromov's theorem on groups of polynomial growth, first proved by Mikhail Gromov, characterizes finitely generated groups of ''polynomial'' growth, as those groups which have nilpotent subgroups of finite index.
Statement ...
*
Non-standard calculus
In mathematics, nonstandard calculus is the modern application of infinitesimals, in the sense of nonstandard analysis, to infinitesimal calculus. It provides a rigorous justification for some arguments in calculus that were previously considered m ...
References
*
*
*
*
* {{cite journal , first = Mihir , last = Bellare , date = 1997 , citeseerx = 10.1.1.43.7900 , title = A Note on Negligible Functions , journal = Journal of Cryptology , volume = 15 , page = 2002 , publisher = Dept. of Computer Science & Engineering University of California at San Diego
Mathematical analysis
Types of functions