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 [1].
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 [2]. 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 [3]
[math]\displaystyle{ \widehat{f}(u)=\sum_{x \in \mathbb{F}_2^n}(-1)^{f(x) \oplus x \cdot u}. }[/math]
- ↑ Carlet C. Boolean Functions for Cryptography and Coding Theory. Cambridge University Press; 2021.
- ↑ 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.