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<ref>{{#invoke:Vorlage:Literatur|f}}</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ä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>{{#invoke:Vorlage:Literatur|f}}</ref>.
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
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 linear oder affin.
Einzelnachweise
<references />
Weblinks
- {{#invoke:Vorlage:Literatur|f}}{{#if:
| {{#if: Vorlage:Cite book/ParamBool
| Vorlage:Toter Link/archivebot
| Vorlage:Webarchiv/archiv-bot
}}
}}{{#invoke:TemplatePar|check
|all = title=
|opt = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical= name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx= accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
|errNS = 0
|template = Vorlage:Cite journal
|format =
|preview = 1
}}Vorlage:Cite book/URL{{#if: | Vorlage:Cite book/Meldung }}{{#if: | Vorlage:Cite book/Meldung }}{{#if: IEEE Transactions on Information Theory
|| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:T. Siegenthaler|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}