Vernachlässigbare Funktion

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

Eine Funktion $f\colon \mathbb {N} \rightarrow \mathbb {R}$ heißt vernachlässigbar, wenn Folgendes gilt:

Zu jedem positiven Polynom $p$ existiert eine Schwelle $m_{p}$ , ab der für alle $n>m_{p}$ gilt:

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

.

Eine äquivalente Formulierung ist: Zu jeder positiven Konstante $c$ existiert eine Schwelle $m_{c}$ , ab der für alle $n>m_{c}$ gilt:

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

.

Beispiele und Gegenbeispiele

Jede Folge, die exponentiell gegen Null strebt, wie z. B. $f(n)={\frac {1}{2^{n}}}$ , ist vernachlässigbar.

Hingegen sind etwa die Folge $f(n)={\frac {1}{q(n)}}$ für ein festes, positives Polynom $q$ oder $f(n)={\frac {1}{\log _{2}(n)}}$ nicht vernachlässigbar.

Anwendung

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

Oded Goldreich: Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press, 2001, ISBN 0-521-79172-3, Kapitel 2: Computational Difficulty (Auszüge aus einer früheren Version).
Dominique Unruh: Protokollkomposition und Komplexität (Dissertation). Universität Karlsruhe (TH), Karlsruhe 2006, S. 16 (PDF).