Harman Patil (Editor)

Correlation immunity

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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 , … , x n is statistically independent of the value of f ( x 1 , x 2 , … , x n ) .

Contents

Definition

A function f : F 2 n → F 2 is k -th order correlation immune if for any independent n binary random variables X 0 … X n − 1 , the random variable Z = f ( X 0 , … , X n − 1 ) is independent from any random vector ( X i 1 … X i k ) with 0 ≤ i 1 < … < i k < n .

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.

References

Correlation immunity Wikipedia
(Text) CC BY-SA