In mathematics, the correlation immunity of a

Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth 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

statistically independent Independence is a fundamental notion in probability theory, as in statistics and the theory of stochastic processes. Two events are independent, statistically independent, or stochastically independent if, informally speaking, the occurrence of ...

of the value of

f(x_1,x_2,\ldots,x_n)

Definition

A function

f:\mathbb_2^n\rightarrow\mathbb_2

k

-th order correlation immune if for any independent

n

binary random variables

X_0\ldots X_

, the random variable

Z=f(X_0,\ldots,X_)

is independent from any random vector

(X_\ldots X_)

with

0\leq i_1<\ldots .

Results in cryptography

When used in a

stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream ( keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...

as a combining function for

linear feedback shift register In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a s ...

s, a Boolean function with low-order correlation-immunity is more susceptible to a

correlation attack In cryptography, correlation attacks are a class of known-plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear-feedback shift registers (LFSRs) using a Boolean function. Correlatio ...

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.

Definition

Results in cryptography

References

Further reading