Correlation immunity

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

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].

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 | Quelltext 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]).