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 function [math]\displaystyle{ f }[/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 [1]. 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
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 [2]
[math]\displaystyle{ \widehat{f}(u)=\sum_{x \in F_2^{n}(-1)^{f(x) \oplus x \cdot u}, }[/math]
- ↑ Siegenthaler, T. (1984). “Correlation-immunity of nonlinear combining functions for cryptographic applications.” IEEE Transactions on Information theory, IT-30 (5), 776–780.
- ↑ Xiao, Guo-Zhen and J.L. Massey (1988). “A spectral characterization of correlation-immune combining functions.” IEEE Trans. Inf. Theory, IT-34 (3), 569– 571.