 #jsDisabledContent { display:none; } My Account | Register | Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

Correlation immunity

Article Id: WHEBN0004279403
Reproduction Date:

 Title: Correlation immunity Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

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.