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_2^n\rightarrow\mathbb_2$ is $k$-th order correlation immune if for any independent $n$ binary random variables $X_0\ldots X_$, the random variable $Z=f(X_0,\ldots,X_)$ is independent from any random vector $(X_\ldots X_)$ with 0\leq i_1<\ldots.

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

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

Cryptography
Boolean algebra

{{crypto-stub