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 <math>f(x_1,x_2,\dots,x_n)</math> is a Boolean function that takes the outputs of <math>n</math> individual generators <math>(x_1,x_2,\dots,x_n)</math> as inputs and produces a single output bit at each step. The choice of <math>f</math> significantly affects the cryptographic strength of the system, such as its resilience to correlation attacks, balance properties, and algebraic complexity.

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

Correlation immunity

Definition

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

Using, Walsh transform below, the Boolean function <math>f</math> is <math>m</math>-th order correlation immune if and only if <math>\widehat{f}(u)=0</math>, for all <math>u \in \mathbb{F}_2^n</math>, s.t. <math>1 \leq w_H(u) \leq m,</math>, where <math>w_H(u)</math> is the Hamming weight of <math>u</math>.

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 <math>m</math>-th order correlation-immune, then there exist a correlation between the output of the function and <math>m</math> coordinated of its input. Moreover, if <math>m</math> 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 <math>m </math>-th order correlation-immune functions are called <math>m </math>-resilient functions.

Using, Walsh transform below, the Boolean function <math>f</math> is <math>m</math>-resilient if and only if <math>\widehat{f}(u)=0</math>, for all <math>u \in \mathbb{F}_2^n</math>, s.t. <math>w_H(u) \leq m,</math>.

The maximum value of <math>m </math> such that <math>f</math> is <math>m </math>-resilient is called the resiliency order of <math>f</math>.

Walsh transform of correlation immunity and resiliency

Correlation immunity and resiliency can be characterized through the Walsh transform

<math>\widehat{f}(u)=\sum_{x \in \mathbb{F}_2^n}(-1)^{f(x) \oplus x \cdot u}.</math>

Example

Let <math>r </math> be a positive integer smaller than <math>n </math>. Let <math>g </math> be any Boolean function on <math>\mathbb{F}_2^{n-r} </math> and let <math>\phi </math> be a mapping, s.t. <math>\phi : \mathbb{F}_2^{n-r} \mapsto \mathbb{F}_2^{r} </math>. Define the function <math>f_{\phi , g}(x, y) </math> for <math>x \in \mathbb{F}_2^r, \; y \in \mathbb{F}_2^{n-r} </math>, s.t.

<math>f_{\phi , g}(x, y)=x \cdot \phi(y) \oplus g(y)=\bigoplus_{i=1}^r x_i \phi_i(y) \oplus g(y), </math>

where <math>\phi_i(y) </math> is the <math>i </math>-th coordinate of <math>\phi(y) </math>. Then <math>f_{\phi , g}(x, y) </math> is <math>m </math>-resilient with <math>m \geq k </math> if every element in <math>\phi(\mathbb{F}_2^{n-r}) </math> has Hamming weight strictly greater than <math>k </math> .