Vernachlässigbare Funktion

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Eine vernachlässigbare Funktion ist eine reellwertige Nullfolge, die schneller gegen Null strebt als das Inverse jedes Polynoms. Obwohl der Begriff vernachlässigbare Folge treffender wäre, wird er nur selten verwendet. Vernachlässigbare Funktionen werden bei asymptotischen Betrachtungen in der Kryptologie eingesetzt, um sehr kleine Wahrscheinlichkeiten formal zu beschreiben.

Eine Funktion heißt vernachlässigbar, wenn Folgendes gilt:

Zu jedem positiven Polynom existiert eine Schwelle , ab der für alle gilt:

.

Eine äquivalente Formulierung ist: Zu jeder positiven Konstante existiert eine Schwelle , ab der für alle gilt:

.

Beispiele und Gegenbeispiele

[Bearbeiten | Quelltext bearbeiten]

Jede Folge, die exponentiell gegen Null strebt, wie z. B. , ist vernachlässigbar.

Hingegen sind etwa die Folge für ein festes, positives Polynom oder nicht vernachlässigbar.

In der beweisbaren Sicherheit gilt bei einem System ein Sicherheitsziel gegen eine Angreiferklasse als erreicht, wenn jeder Angreifer aus der Klasse die Sicherheit nur mit einer Wahrscheinlichkeit brechen kann, die höchstens vernachlässigbar im Sicherheitsparameter ist. Eine Public-Key-Verschlüsselung ist also IND-CPA, wenn jeder polynomial beschränkte Angreifer die Verschlüsselung zweier beliebiger Nachrichten nur mit vernachlässigbarer Wahrscheinlichkeit unterscheiden kann. Die Wahrscheinlichkeit hängt hier vom Sicherheitsparameter ab, der auch die Länge der Schlüssel bestimmt. Praktisch bedeutet das, dass eine Erhöhung des Sicherheitsparameters (und damit der Schlüssellänge) die Erfolgswahrscheinlichkeit des Angreifers stark senkt.