imported>Ulanwp: 3 fehlende Sprachparameter eingefügt; 1 Datumsformat konvertiert

2026-02-20T14:05:58Z

3 fehlende Sprachparameter eingefügt; 1 Datumsformat konvertiert

Neue Seite

Die '''correlation immunity''' (Korrelationsimmunität) ist ein Maß dafür, ob und wie viel Information man aus dem Funktionswert einer [[Boolesche Funktion|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<ref>{{Literatur |Autor=T. Siegenthaler |Titel=Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.) |Sammelwerk=IEEE Transactions on Information Theory |Band=30 |Nummer=5 |Datum=1984-09 |Seiten=776–780 |ISSN=0018-9448 |DOI=10.1109/tit.1984.1056949 |Online=[http://ieeexplore.ieee.org/document/1056949/ Online] |Abruf=2018-02-14 |Sprache=en}}</ref>.

== Definition ==
Sei <math>f\colon \mathbb{F}_2^n\rightarrow\mathbb{F}_2</math> eine Boolesche Funktion und seien <math>X_1, X_2, \ldots, X_n</math> binäre [[Unabhängig und identisch verteilte Zufallsvariablen|unabhängige und identisch verteilte Zufallsvariablen]], die die Argumente für <math>f</math> repräsentieren. Eine Funktion <math>f</math> ist korrelationsimmun der Ordnung <math>m</math> genau dann, wenn der Funktionswert <math>f(X_1, X_2, \dots, X_n)</math> statistisch unabhängig von den Eingabewerten <math>X_1, X_2, \dots, X_n</math> ist und zwar genau für jede Auswahl aus <math>m</math> Indizes (oder weniger) <math>i_1,i_2,\ldots,i_m</math>, mit <math>1\leq i_1 < i_2 < \ldots i_m \leq n</math>. Direkt äquivalent dazu ist die Aussage, dass die gegenseitige Information der <math>m</math> oder weniger Eingabewerte <math>X_{i_1},X_{i_2},\ldots ,X_{i_m}</math> und des Funktionswertes <math>f(X_1, X_2, \dots, X_n)</math> gleich 0 ist, also
:<math>I(X_{i_1},X_{i_2},\ldots ,X_{i_m};f(X_1, X_2, \dots, X_n))=0.</math>

Wenn die Funktion <math>f</math> zusätzlich gleichverteilt ist, also <math>\Pr(f(X_1,\ldots X_n )=0)=\Pr(f(X_1,\ldots X_n )=1) = \frac{1}{2}</math>, dann heißt <math>f</math> <math>m</math>-resilient<ref>{{Literatur |Autor=B. Chor, O. Goldreich, J. Hasted, J. Freidmann, S. Rudich |Titel=The bit extraction problem or t-resilient functions |Sammelwerk=26th Annual Symposium on Foundations of Computer Science (sfcs 1985) |Datum=1985-10 |Seiten=396–407 |DOI=10.1109/SFCS.1985.55 |Online=[http://ieeexplore.ieee.org:80/document/4568165/?reload=true Online] |Abruf=2018-02-14 |Sprache=en}}</ref>.

Doch diese [[Notwendige und hinreichende Bedingung|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'' ==
Zusätzlich zur Definition von Korrelationsimmunität gibt Siegenthaler auch gleichzeitig einen wichtigen Trade-off zwischen der Korrelationsimmunität und dem Grad einer Funktion <math>f</math>. Wenn <math>f</math> korrelationsimmun der Ordnung <math>m</math> ist, <math>1\leq m \leq n-1</math>, dann ist der Grad von <math>f</math> <math>\deg(f)\leq n - m + 1</math>. Wenn <math>f</math> zusätzlich gleichverteilt ist, also <math>m</math>-resilient, dann ist der Grad von <math>f</math> sogar <math>\deg(f)\leq n - m</math>.

Das heißt, dass der korrelationsimmune Funktionen der höchsten Ordnung immer einen kleinen Grad haben. So sind zum Beispiel <math>(n-1)</math>-resiliente Funktionen immer vom Grad 1 oder kleiner, also [[Lineare Abbildung|linear]] oder [[Affine Abbildung|affin]].

== Einzelnachweise ==
<references />

== Weblinks ==
* {{cite journal |author=T. Siegenthaler |date=September 1984 |title=Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications |journal=IEEE Transactions on Information Theory |volume=30 |issue=5 |pages=776–780 |doi=10.1109/TIT.1984.1056949 |language=en}}
* http://www.iaik.tugraz.at/teaching/00_angewandte%20kryptografie/slides2008/streamciphers.pdf (PDF-Datei; 15 kB)

[[Kategorie:Kryptologie]]

Correlation immunity - Versionsgeschichte

imported>Ulanwp: 3 fehlende Sprachparameter eingefügt; 1 Datumsformat konvertiert