Negligible function

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

definition

A function is said to be negligible if: ${\ displaystyle f \ colon \ mathbb {N} \ rightarrow \ mathbb {R}}$

For every positive polynomial there is a threshold from which applies to all : ${\ displaystyle p}$ ${\ displaystyle m_ {p}}$ ${\ displaystyle n> m_ {p}}$

{\ displaystyle | f (n) | <{\ frac {1} {p (n)}}}

.

An equivalent formulation is: For every positive constant there is a threshold from which the following applies to all : ${\ displaystyle c}$ ${\ displaystyle m_ {c}}$ ${\ displaystyle n> m_ {c}}$

{\ displaystyle | f (n) | <{\ frac {1} {n ^ {c}}}}

.

Examples and counterexamples

Any sequence that tends exponentially to zero, such as B. , is negligible. ${\ displaystyle f (n) = {\ frac {1} {2 ^ {n}}}}$

In contrast, the consequences for a fixed, positive polynomial are or not negligible. ${\ displaystyle f (n) = {\ frac {1} {q (n)}}}$ ${\ displaystyle q}$ ${\ displaystyle f (n) = {\ frac {1} {\ log _ {2} (n)}}}$

application

In terms of provable security , a security goal against an attacker class is considered to have been achieved in a system if each attacker from the class can only break the security with a probability that is at most negligible in the security parameter. A public-key encryption is thus IND-CPA if every polynomial limited attacker can distinguish the encryption of any two messages only with negligible probability. The probability here depends on the security parameter, which also determines the length of the key. In practical terms, this means that increasing the security parameter (and thus the key length) greatly reduces the attacker's probability of success.

literature

Oded Goldreich : Foundations of Cryptography: Volume 1, Basic Tools . Cambridge University Press, 2001, ISBN 0-521-79172-3 , Chapter 2: Computational Difficulty ( excerpts from an earlier version ).
Dominique Unruh: Protocol Composition and Complexity (Dissertation) . University of Karlsruhe (TH), Karlsruhe 2006, p. 16 ( PDF ).