Inmunidad correlativa

En matemáticas, la inmunidad a la correlación de una función booleana es una medida del grado en que sus salidas no están correlacionadas con algún subconjunto de sus entradas. Específicamente, se dice que una función booleana es inmune a la correlación de orden m si cada subconjunto de m o menos variables en es estadísticamente independiente del valor de . ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}$

Una función es inmune a la correlación de orden -ésimo si para cualesquiera variables aleatorias binarias independientes , la variable aleatoria es independiente de cualquier vector aleatorio con . ${\displaystyle f:\mathbb {F} _{2}^{n}\rightarrow \mathbb {F} _{2}}$${\displaystyle k}$${\displaystyle n}$${\displaystyle X_{0}\ldots X_{n-1}}$${\displaystyle Z=f(X_{0},\ldots ,X_{n-1})}$${\displaystyle (X_{i_{1}}\ldots X_{i_{k}})}$${\displaystyle 0\leq i_{1}<\ldots <i_{k}<n}$

Cuando se utiliza en un cifrado de flujo como función de combinación para registros de desplazamiento de retroalimentación lineal , una función booleana con inmunidad a la correlación de orden bajo es más susceptible a un ataque de correlación que una función con inmunidad a la correlación de orden alto .

Siegenthaler demostró que la inmunidad de correlación m de una función booleana de grado algebraico d de n variables satisface m  +  d  ≤  n ; para un conjunto dado de variables de entrada, esto significa que un grado algebraico alto restringirá la inmunidad de correlación máxima posible. Además, si la función es balanceada, entonces m  +  d  ≤  n  − 1. ^{[ 1 ]}

1. Cusick, Thomas W. y Stanica, Pantelimon (2009). «Funciones booleanas criptográficas y aplicaciones». Academic Press. ISBN 9780123748904.