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.

Definition

Bearbeiten

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

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.

Anwendung

Bearbeiten

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.

Literatur

Bearbeiten