Kollisionswahrscheinlichkeit

Die Kollisionswahrscheinlichkeit bezeichnet die Wahrscheinlichkeit, dass bei einer Abbildung von einer Eingabemenge auf eine Ausgabemenge zwei verschiedene Eingaben denselben Ausgabewert erhalten. Sie wird häufig im Kontext von Hash-Funktionen, Zufallszuweisungen oder Datentransfers verwendet, bei denen eine endliche Ausgabemenge existiert.

Gegeben seien n Eingaben, die unabhängig und gleichverteilt in m Ausgabewerte abgebildet werden. Die Wahrscheinlichkeit, dass kein Kollisionsereignis auftritt (alle Ausgaben sind eindeutig), lautet P(no collision) = (m)_n / m^n, wobei (m)_n = m*(m-1)*...*(m-n+1) der fallende Faktor ist. Die Kollisionswahrscheinlichkeit ist P(collision) = 1 - P(no collision) = 1 - (m)_n / m^n.

Für große m und n klein gegenüber m gilt die gute Annäherung P(collision) ≈ 1 - exp(-n(n-1)/(2m)). Für den speziellen Fall eines Kollisionspaares unter zwei zufällig gewählte Eingaben ist P(2 gleiche Ausgabewerte) ungefähr 1/m.

Sogenannte Birthday-Bounds besagen, dass die mittlere Anzahl von Eingaben, die benötigt wird, um mit hoher Wahrscheinlichkeit eine Kollison zu erzeugen, ungefähr sqrt(m) beträgt. Als Beispiel: Bei einer Ausgabemenge der Größe m = 2^32 liegt die Wahrscheinlichkeitsgrenze für eine Kollison bei ungefähr 50%, wenn etwa n ≈ 65.536 Eingaben vorhanden sind.

Anwendungen ergeben sich in der Informatik vor allem bei Hash-Tabellen, Datenspeicherung, Prüfsummen und der Kryptographie. Die Kollisionswahrscheinlichkeit gibt Hinweise darauf, wie groß der Ausgabebereich sein muss, um Kollisionen zu vermeiden oder zu akzeptieren. In der Kryptographie spricht man von Kollisionsresistenz, die beschreibt, wie schwer es ist, zwei verschiedene Eingaben zu finden, die denselben Hashwert erzeugen.

Wichtige Randbedingungen: Die Berechnung setzt voraus, dass die Ausgaben gleichverteilt und unabhängig sind. In der Praxis erfüllen reale Hash-Funktionen diese Annahmen nur annähernd; Abweichungen beeinflussen die tatsächliche Kollisionswahrscheinlichkeit. Daher ist die theoretische Formel eine modellhafte Abschätzung.