Negligible Function

Introduction:

Modern cryptography concerns about infeasibility rather than impossibility. For example, an encryption scheme is said to be provably secure if the success probability of "breaking" by an adversary is negligibly small rather than zero. Theoretically, the probability is expressed as a probability function of a security parameter k, which is normally the cryptographic key length. Infeasiblity relies on that the success probability function to be a negligible function.

Definition:

A function $f$ is negligible if for every constant $c \geq 0$ there exists an integer $k_c$ such that $f(k) < k^{-c}$ for all $k \geq k_c$

Notes:

The above definition means that the function $f$ is bounded by any positive polynomial fraction. Since for any positive polynomial fraction $g(x)$, we can always find the smallest $c$ such that $k^{-c} \leq g(x)$ for all $k \geq k_c$. Here, by the meaning of $k \geq k_c$, we can also say that the condition holds for a sufficiently large k.