Correlation immunity and resiliency of Boolean functions

The Boolean functions used in the stream ciphers must be balanced for avoiding statistical dependence between their input and their output .

Combining function, combiner model, combination generator

A combination generator is a running-key generator for stream cipher applications. It is composed of several linear feedback shift registers whose outputs are combined by a Boolean function to produce the keystream. The combining function $f(x_{1},x_{2},\dots ,x_{n})$ is a Boolean function that takes the outputs of $n$ individual generators $(x_{1},x_{2},\dots ,x_{n})$ as inputs and produces a single output bit at each step. The choice of $f$ significantly affects the cryptographic strength of the system, such as its resilience to correlation attacks, balance properties, and algebraic complexity.

Any combination function $f(x)$ used for generating the pseudorandom sequence in the stream cipher must stay balanced if we keep constant some coordinates of $f$.

Correlation immunity

Definition

The Boolean function $f$ is called $m-$order correlation immune if the output distribution probability of $f$ is unaltered when any $m$ of its input bits are kept constant.

Using, Walsh transform below, the Boolean function $f$ is $m-$order correlation immune if and only if ${\widehat {f}}(u)=0$, for all $u\in \mathbb {F} _{2}^{n}$, s.t. $1\leq w_{H}(u)\leq m,$, where $w_{H}(u)$ is the Hamming weight of $u$.

Importance of correlation-immune functions

The notion of correlation-immune function is related to the notion of orthogonal array. The notion of correlation immunity was introduced by Siegenthaler . If combining function is not $m-$th order correlation-immune, then there exist a correlation between the output of the function and $m$ coordinated of its input. Moreover, if $m$ is small enough ― a divide-and-conquer attack, correlation attack for stream ciphers, and later improved to fast correlation attack ― uses this weakness for attacking the system.

Resiliency

Definition

Balanced $m$-th order correlation-immune functions are called $m$-resilient functions.

Using, Walsh transform below, the Boolean function $f$ is $m-$resilient if and only if ${\widehat {f}}(u)=0$, for all $u\in \mathbb {F} _{2}^{n}$, s.t. $w_{H}(u)\leq m,$.

The maximum value of $m$ such that $f$ is $m$-resilient is called the resiliency order of $f$.

Walsh transform of correlation immunity and resiliency

Correlation immunity and resiliency can be characterized through the Walsh transform

${\widehat {f}}(u)=\sum _{x\in \mathbb {F} _{2}^{n}}(-1)^{f(x)\oplus x\cdot u}.$