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

Sei ${\displaystyle f\colon \mathbb {F} _{2}^{n}\rightarrow \mathbb {F} _{2}}$ eine Boolesche Funktion und seien ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$ binäre unabhängige und identisch verteilte Zufallsvariablen, die die Argumente für ${\displaystyle f}$ repräsentieren. Eine Funktion ${\displaystyle f}$ ist korrelationsimmun der Ordnung ${\displaystyle m}$ genau dann, wenn der Funktionswert ${\displaystyle f(X_{1},X_{2},\dots ,X_{n})}$ statistisch unabhängig von den Eingabewerten ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$ ist und zwar genau für jede Auswahl aus ${\displaystyle m}$ Indizes (oder weniger) ${\displaystyle i_{1},i_{2},\ldots ,i_{m}}$, mit ${\displaystyle 1\leq i_{1}<i_{2}<\ldots i_{m}\leq n}$. Direkt äquivalent dazu ist die Aussage, dass die gegenseitige Information der ${\displaystyle m}$ oder weniger Eingabewerte ${\displaystyle X_{i_{1}},X_{i_{2}},\ldots ,X_{i_{m}}}$ und des Funktionswertes ${\displaystyle f(X_{1},X_{2},\dots ,X_{n})}$ gleich 0 ist, also

${\displaystyle I(X_{i_{1}},X_{i_{2}},\ldots ,X_{i_{m}};f(X_{1},X_{2},\dots ,X_{n}))=0.}$

Wenn die Funktion ${\displaystyle f}$ zusätzlich gleichverteilt ist, also ${\displaystyle \Pr(f(X_{1},\ldots X_{n})=0)=\Pr(f(X_{1},\ldots X_{n})=1)={\frac {1}{2}}}$, dann heißt ${\displaystyle f}$ ${\displaystyle m}$-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.

Zusätzlich zur Definition von Korrelationsimmunität gibt Siegenthaler auch gleichzeitig einen wichtigen Trade-off zwischen der Korrelationsimmunität und dem Grad einer Funktion ${\displaystyle f}$. Wenn ${\displaystyle f}$ korrelationsimmun der Ordnung ${\displaystyle m}$ ist, ${\displaystyle 1\leq m\leq n-1}$, dann ist der Grad von ${\displaystyle f}$ ${\displaystyle \deg(f)\leq n-m+1}$. Wenn ${\displaystyle f}$ zusätzlich gleichverteilt ist, also ${\displaystyle m}$-resilient, dann ist der Grad von ${\displaystyle f}$ sogar ${\displaystyle \deg(f)\leq n-m}$.

Das heißt, dass der korrelationsimmune Funktionen der höchsten Ordnung immer einen kleinen Grad haben. So sind zum Beispiel ${\displaystyle (n-1)}$-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]). 

• T. Siegenthaler: Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications. In: IEEE Transactions on Information Theory. 30. Jahrgang, 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)