Correlation immunity explained

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: F ^{n → 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.^[1]

References

Further reading

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

Notes and References

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