Correlation immunity

From Wikipedia, the free encyclopedia

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)$ .

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 is in conflict with its algebraic degree d, such that m + d ≤ n. Furthermore, if the function is balanced then m + d ≤ n − 1.

[edit] References

T. Siegenthaler (September 1984). "Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications". IEEE Transactions on Information Theory 30 (5): 776–780. doi:10.1109/TIT.1984.1056949.