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-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.