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. Der Begriff der Korrelationsimmunität für Boolesche Funktionen wurde zuerst von Siegenthaler definiert[1].

Definition

Bearbeiten

Sei   eine Boolesche Funktion und seien   binäre unabhängige und identisch verteilte Zufallsvariablen, die die Argumente für   repräsentieren. Eine Funktion   ist korrelationsimmun der Ordnung   genau dann, wenn der Funktionswert   statistisch unabhängig von den Eingabewerten   ist und zwar genau für jede Auswahl aus   Indizes (oder weniger)  , mit  . Direkt äquivalent dazu ist die Aussage, dass die gegenseitige Information der   oder weniger Eingabewerte   und des Funktionswertes   gleich 0 ist, also

 

Wenn die Funktion   zusätzlich gleichverteilt ist, also  , dann heißt    -resilient[2].

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.

Trade-off zwischen Korrelationsimmunität und Grad von f

Bearbeiten

Zusätzlich zur Definition von Korrelationsimmunität gibt Siegenthaler auch gleichzeitig einen wichtigen Trade-off zwischen der Korrelationsimmunität und dem Grad einer Funktion  . Wenn   korrelationsimmun der Ordnung   ist,  , dann ist der Grad von    . Wenn   zusätzlich gleichverteilt ist, also  -resilient, dann ist der Grad von   sogar  .

Das heißt, dass der korrelationsimmune Funktionen der höchsten Ordnung immer einen kleinen Grad haben. So sind zum Beispiel  -resiliente Funktionen immer vom Grad 1 oder kleiner, also linear oder affin.

  1. T. Siegenthaler: Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.). In: IEEE Transactions on Information Theory. Band 30, Nr. 5, September 1984, ISSN 0018-9448, S. 776–780, doi:10.1109/tit.1984.1056949 (ieee.org [abgerufen am 14. Februar 2018]).
  2. B. Chor, O. Goldreich, J. Hasted, J. Freidmann, S. Rudich: The bit extraction problem or t-resilient functions. In: 26th Annual Symposium on Foundations of Computer Science (sfcs 1985). Oktober 1985, S. 396–407, doi:10.1109/SFCS.1985.55 (ieee.org [abgerufen am 14. Februar 2018]).
Bearbeiten