Correlation immunity

In mathematics, the correlation immunity of a Boolean function is a measure of the degree to which its outputs are uncorrelated with some subset of its inputs. Specifically, a Boolean function is said to be correlation-immune of order m if every subset of m or fewer variables in $x_{1},x_{2},\ldots ,x_{n}$ is statistically independent of the value of $f(x_{1},x_{2},\ldots ,x_{n})$.

Definition

A function $f:{\mathbb {F}}_{2}^{n}\rightarrow {\mathbb {F}}_{2}$ is $k$-th order correlation immune if for any independent $n$ binary random variables $X_{0}\ldots X_{{n-1}}$, the random variable $Z=f(X_{0},\ldots ,X_{{n-1}})$ is independent from any random vector $(X_{{i_{1}}}\ldots X_{{i_{k}}})$ with $0\leq i_{1}<\ldots <i_{k}<n$.

Results in cryptography

When used in a stream cipher as a combining function for linear feedback shift registers, a Boolean function with low-order correlation-immunity is more susceptible to a correlation attack than a function with correlation immunity of high order.

Siegenthaler showed that the correlation immunity m of a Boolean function of algebraic degree d of n variables satisfies m + d ≤ n; for a given set of input variables, this means that a high algebraic degree will restrict the maximum possible correlation immunity. Furthermore, if the function is balanced then m + d ≤ n − 1.

References

Further reading

1. Cusick, Thomas W. & Stanica, Pantelimon (2009). "Cryptographic Boolean functions and applications". Academic Press. ISBN 9780123748904.