Korrelationsimmunitet

I matematik är korrelationsimmuniteten för en boolesk funktion ett mått på i vilken grad dess utdata är okorrelerade med någon delmängd av dess indata. Specifikt sägs en boolesk funktion vara korrelationsimmun av ordningen m om varje delmängd av m eller färre variabler i $x_{1},x_{2},\ldots , x_{n}$ är statistiskt oberoende av värdet på $f(x_{1},x_{2},\ldots ,x_{n})$ .

Definition

En funktion $f:\mathbb {F} _{2}^{n}\rightarrow \mathbb {F} _{2}$ är $k$ -te ordningen korrelationsimmun om för alla oberoende $n$ binära slumpvariabler $X_{0}\ldots X_{n-1}$ , den slumpmässiga variabeln $Z=f(X_{0},\ldots ,X_{n-1})$ är oberoende av vilken slumpmässig vektor som helst $(X_{i_{ 1}}\ldots X_{i_{k}})$ med $0\leq i_{1}<\ldots <i_{k}<n$ .

Resultat i kryptografi

När den används i ett strömchiffer som en kombinerande funktion för linjära återkopplingsskiftregister , är en boolesk funktion med låg ordningens korrelationsimmunitet mer mottaglig för en korrelationsattack än en funktion med korrelationsimmunitet av hög ordning .

Siegenthaler visade att korrelationsimmuniteten m för en boolesk funktion av algebraisk grad d av n variabler uppfyller m + d ≤ n ; för en given uppsättning indatavariabler betyder detta att en hög algebraisk grad kommer att begränsa den maximala möjliga korrelationsimmuniteten. Dessutom, om funktionen är balanserad så är m + d ≤ n − 1.

Vidare läsning

1.   Cusick, Thomas W. & Stanica, Pantelimon (2009). "Kryptografiska booleska funktioner och applikationer". Akademisk press. ISBN 9780123748904 .