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>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>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>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 [2]. 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 [3]
<math>\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.