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 formula_1 is statistically independent of the value of formula_2. Definition. A function formula_3 is formula_4-th order correlation immune if for any independent formula_5 binary random variables formula_6, the random variable formula_7 is independent from any random vector formula_8 with formula_9. 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.