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]\displaystyle{ f(x_1,x_2,\dots,x_n) }[/math] is a Boolean function that takes the outputs of [math]\displaystyle{ n }[/math] individual generators [math]\displaystyle{ (x_1,x_2,\dots,x_n) }[/math] as inputs and produces a single output bit at each step. The choice of [math]\displaystyle{ 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]\displaystyle{ f(x) }[/math] used for generating the pseudorandom sequence in the stream cipher must stay balanced if we keep constant some coordinates of [math]\displaystyle{ f }[/math].

Correlation immunity

Definition

The Boolean function [math]\displaystyle{ f }[/math] is called [math]\displaystyle{ m- }[/math]order correlation immune if the output distribution probability of [math]\displaystyle{ f }[/math] is unaltered when any [math]\displaystyle{ m }[/math] of its input bits are kept constant.

Using, Walsh transform below, the Boolean function [math]\displaystyle{ f }[/math] is [math]\displaystyle{ m- }[/math]order correlation immune if and only if [math]\displaystyle{ \widehat{f}(u)=0 }[/math], for all [math]\displaystyle{ u \in \mathbb{F}_2^n }[/math], s.t. [math]\displaystyle{ 1 \leq w_H(u) \leq m, }[/math], where [math]\displaystyle{ w_H(u) }[/math] is the Hamming weight of [math]\displaystyle{ 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]\displaystyle{ m- }[/math]th order correlation-immune, then there exist a correlation between the output of the function and [math]\displaystyle{ m }[/math] coordinated of its input. Moreover, if [math]\displaystyle{ 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]\displaystyle{ m }[/math]-th order correlation-immune functions are called [math]\displaystyle{ m }[/math]-resilient functions.

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

The maximum value of [math]\displaystyle{ m }[/math] such that [math]\displaystyle{ f }[/math] is [math]\displaystyle{ m }[/math]-resilient is called the resiliency order of [math]\displaystyle{ f }[/math].

Walsh transform of correlation immunity and resiliency

Correlation immunity and resiliency can be characterized through the Walsh transform

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

Example

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

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