Negligible function

A negligible function is a real-valued zero sequence that tends to zero faster than the inverse of any polynomial. Although the term negligible consequence would be more accurate, it is rarely used. Negligible functions are used in asymptotic considerations in cryptology to describe very small probabilities formal.

Definition

A function is called negligible if the following applies:

For every positive polynomial exists a threshold above which applies to all:

An equivalent formulation is: For every positive constant exists a threshold above which applies to all:

Examples and counter-examples

Each episode that strives exponentially to zero, such as, Is negligible.

In contrast, as the result of a strong, positive polynomial or not negligible.

Application

In the provable security applies to a system, a safety goal against attackers class to be reached when each attacker out of the class can break the security only with a probability that is at most negligible in the security parameter. A public-key encryption is IND - CPA so if any polynomially bounded attacker can distinguish the encryption of any two messages only with negligible probability. The probability here depends on the security parameter, which determines the length of the key. In practice this means that an increase in the security parameter (and thus the key length ) greatly lowers the success probability of the attacker.