Correlation immunity

From Wikipedia, the free encyclopedia

The correlation immunity of a boolean function is a measure of the degree to which its outputs are correlated 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).

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 is in conflict with its algebraic degree d, such that m + d \le n. Furthermore, if the function is balanced then m + d \le n-1.

[edit] References

  • T. Siegenthaler (September 1984). "Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications". IEEE Transactions on Information Theory 30 (5): 776–780.
 This cryptography-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../c/o/r/Correlation_immunity.html"