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 <math>x_1,x_2,\ldots,x_n</math> is statistically independent of the value of <math>f(x_1,x_2,\ldots,x_n)</math>.
== Definition == A function <math>f:\mathbb{F}_2^n\rightarrow\mathbb{F}_2</math> is <math>k</math>-th order correlation immune if for any independent <math>n</math> binary random variables <math>X_0\ldots X_{n-1}</math>, the random variable <math>Z=f(X_0,\ldots,X_{n-1})</math> is independent from any random vector <math>(X_{i_1}\ldots X_{i_k})</math> with <math>0\leq i_1<\ldots<i_k<n</math>.
== 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.<ref name="Siegenthaler">{{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 }}</ref>
==References== {{reflist}}
===Further reading=== # Cusick, Thomas W. & Stanica, Pantelimon (2009). "Cryptographic Boolean functions and applications". Academic Press. {{ISBN|9780123748904}}.
{{Cryptography navbox | block | hash | stream}}
Category:Cryptography Category:Boolean algebra
{{crypto-stub}}