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{F}_2^n\rightarrow\mathbb{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 .$

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.{{cite journal | author=T. Siegenthaler | title=Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications | journal=IEEE Transactions on Information Theory |date=September 1984 | volume=30 | issue=5 | pages=776–780 | doi=10.1109/TIT.1984.1056949 }}

References

=Further reading=

Cusick, Thomas W. & Stanica, Pantelimon (2009). "Cryptographic Boolean functions and applications". Academic Press. {{ISBN|9780123748904}}.

Category:Cryptography

Category:Boolean algebra