Correlation immunity

Die correlation immunity (Korrelationsimmunität) ist ein Maß dafür, ob und wie viel Information man aus dem Funktionswert einer booleschen Funktion über deren Argumente ziehen kann.

In der Kryptographie zeigt sie an, wie resistent eine boolesche Funktion gegen Korrelationsattacken ist.

Eine notwendige Bedingung für die correlation immunity ist die Gleichverteilung der Ausgabe einer Funktion: Eine Funktion $f(X_1, X_2, \dots, X_n)$ ist genau dann correlation immune wenn^[1]:

$P(f = X_i) = \frac{1}{2}\,\,\,\,\, \forall i,\, 1 \leq i \leq n$

Ist diese Bedingung erfüllt, so ist eine Null oder eine Eins für f gleich wahrscheinlich.

Doch diese notwendige Bedingung sagt nur aus ob eine Funktion überhaupt correlation immune ist oder nicht. Besser wäre es, wenn man einen Wert für eine Funktion finden würde, die den Grad der Immunität angibt. Genau das wird auch für die Definition des Siegenthaler bound benötigt.

Eine Funktion f ist correlation immune mit der Ordnung m genau dann, wenn der Funktionswert $f(X_1, X_2, \dots, X_n)$ statistisch unabhängig von den Eingabewerten $X_1, X_2, \dots, X_n$ ist und zwar genau für jede Kombination aus m Eingabevariablen und weniger.

Quellen

1. ↑ http://www.isical.ac.in/~crg/tech_reports/tech9.ps

Weblinks

• T. Siegenthaler: Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications. In: IEEE Transactions on Information Theory. 30, Nr. 5, September 1984, S. 776–780. doi:10.1109/TIT.1984.1056949.
• http://www.iaik.tugraz.at/teaching/00_angewandte%20kryptografie/slides2008/streamciphers.pdf (PDF-Datei; 15 kB)