Negligible function

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 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 = x0 if for every ε > 0, there exists a positive number δ > 0 such that | xx0 | < δ implies | f(x) − f(x0) | < ε.

This classic definition of continuity can be transformed into the definition of negligibility in a few steps by changing a parameter used in the definition per step. First, in case x_0=\infty with f(x0) = 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 ε > 0 there exists N_{\epsilon} such that for all x>N_{\epsilon}
|\mu(x)|<\epsilon\,.[citation needed]

Next, we replace ε > 0 by the functions 1 / xc 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.

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

  • Goldreich, Oded (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the author's web site.
  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 10.6.3: One-way functions, pp.374–376.
  • Christos Papadimitriou (1993). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1.  Section 12.1: One-way functions, pp.279–298.
  • Jean François Colombeau (1984). New Generalized Functions and Multiplication of Distributions. Mathematics Studies 84, North Holland. ISBN 0-444-86830-5. 

See also


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Negligible (disambiguation) — Negligible may refer to: Negligible having an insignificant effect In mathematics, the Negligible function This disambiguation page lists articles associated with the same title. If an internal link l …   Wikipedia

  • Negligible — Not to be confused with the Negligible function. Negligible refers to the quantities so small that they can be ignored (neglected) when studying the larger effect. Although related to the more mathematical concepts of infinitesimal, the idea of… …   Wikipedia

  • Negligible set — See also: Generic property 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… …   Wikipedia

  • Strategies for Engineered Negligible Senescence — (SENS) is the name Aubrey de Grey gives to his proposal to research regenerative medical procedures to periodically repair all the age related damage in the human body, thereby maintaining a youthful state indefinitely.[1][2] The term first… …   Wikipedia

  • Partition function (statistical mechanics) — For other uses, see Partition function (disambiguation). Partition function describe the statistical properties of a system in thermodynamic equilibrium. It is a function of temperature and other parameters, such as the volume enclosing a gas.… …   Wikipedia

  • Likelihood function — In statistics, a likelihood function (often simply the likelihood) is a function of the parameters of a statistical model, defined as follows: the likelihood of a set of parameter values given some observed outcomes is equal to the probability of …   Wikipedia

  • One-way function — Unsolved problems in computer science Do one way functions exist? 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… …   Wikipedia

  • Differential of a function — For other uses of differential in mathematics, see differential (mathematics). In calculus, the differential represents the principal part of the change in a function y = ƒ(x) with respect to changes in the independent variable. The… …   Wikipedia

  • Generalized function — In mathematics, generalized functions are objects generalizing the notion of functions. There is more than one recognised theory. Generalized functions are especially useful in making discontinuous functions more like smooth functions, and (going …   Wikipedia

  • Naor-Reingold Pseudorandom Function — In 1997, Moni Naor and Omer Reingold described efficient constructions for various cryptographic primitives in private key as well as public key cryptography. Their result is the construction of an efficient pseudorandom function. Let p and l be… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”