Inmunidad de correlación

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. En concreto, 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 . $x_{1},x_{2},\ldots ,x_{n}$ $f(x_{1},x_{2},\ldots ,x_{n})$

Definición

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

Resultados en criptografía

Cuando se utiliza en un cifrado de flujo como una 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 está balanceada, entonces m + d ≤ n − 1. ^[1]

Referencias

^ T. Siegenthaler (septiembre de 1984). "Inmunidad a la correlación de funciones de combinación no lineales para aplicaciones criptográficas". IEEE Transactions on Information Theory . 30 (5): 776–780. doi :10.1109/TIT.1984.1056949.

Lectura adicional

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