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
,
is statistically independent of the value of
A function
-th order correlation immune if for any independent
binary random variables
, the random variable
is independent from any random vector
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.
This cryptography-related article is a stub.
You can help Wikipedia by expanding it.