World Library  
Flag as Inappropriate
Email this Article

Negligible function

Article Id: WHEBN0008426019
Reproduction Date:

Title: Negligible function  
Author: World Heritage Encyclopedia
Language: English
Subject: Very smooth hash, Pseudorandom number generator, Mathematical analysis
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Negligible function

In mathematics, a negligible function is a function \mu(x):\mathbb{N}{\rightarrow}\mathbb{R} such that for every positive integer c there exists an integer Nc such that for all x > Nc,

|\mu(x)|<\frac{1}{x^c}.

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

|\mu(x)|<\frac{1}{\text{poly}(x)}.

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. Lately Cauchy, Weierstrass and Heine also defined as follows (with all numbers in the real number domain \mathbb{R}):

(Continuous function) A function f(x):\mathbb{R}{\rightarrow}\mathbb{R} is continuous at x=x_0 if for every \epsilon>0, there exists a positive number \delta>0 such that |x-x_0|<\delta implies |f(x)-f(x_0)|<\epsilon.

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 x_0=\infty with f(x_0)=0, we must define the concept of "infinitesimal function":

(Infinitesimal) A continuous function \mu(x):\mathbb{R}{\rightarrow}\mathbb{R} is infinitesimal (as x goes to infinity) if for every \epsilon>0 there exists N_{\epsilon} such that for all x>N_{\epsilon}
|\mu(x)|<\epsilon\,.

Next, we replace \epsilon>0 by the functions 1/x^c where c>0 or by 1/poly(x) where poly(x) is a positive polynomial. This leads to the definitions of negligible functions given at the top of this article. Since the constants \epsilon>0 can be expressed as 1/poly(x) with a constant polynomial this shows that negligible functions are a subset of the infinitesimal 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 x = cryptographic key length n. Hence comes the definition at the top of the page because key length n must be a natural number.

Nevertheless, the general notion of negligibility has never said that the system input parameter x must be the key length n. Indeed, x can be any predetermined system metric and corresponding mathematic 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. 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.

References

See also

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.