Correlation immunity and resiliency of Boolean functions

In the standard model of a stream cipher, the outputs of $n$ linear feedback shift registers are the entries of a Boolean function. The output of the function produces the keystream, which is then bitwise xored with the message to produce the cipher. The decryption consists symmetrically in xoring this same keystream with the ciphertext. There are a lot of divide-and-conquer attacks on this method of encryption, see ,,,. To resist these attacks the Boolean function must be properly chosen: balanceness, large algebraic degree, high nonlinearity, and high order correlation immunity .

The Boolean functions used in the stream ciphers must be balanced for avoiding statistical dependence between their input and their output . It must also have large algebraic degree, because its degree conditions are the linear complexity of the produced running-key. A third usual criterion is that the function should be far from all affine functions regarding Hamming distance, since the existence of a “good” approximation of $f$ by an affine function makes fast correlation attacks feasible, see . A fourth criterion on the combining function is that the distribution probability of its output should be unaltered when any $m$ of its inputs are fixed, with m as large as possible. This property, called $m$-th order correlation immunity.

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 $f(x_{1},x_{2},\dots ,x_{n})$ is a Boolean function that takes the outputs of $n$ individual generators $(x_{1},x_{2},\dots ,x_{n})$ as inputs and produces a single output bit at each step. The choice of $f$ significantly affects the cryptographic strength of the system, such as its resilience to correlation attacks, balance properties, and algebraic complexity.

Any combination function $f(x)$ used for generating the pseudorandom sequence in the stream cipher must stay balanced if we keep constant some coordinates of $f$.

Correlation immunity

Definition

The Boolean function $f$ is called $m$-th order correlation immune if the output distribution probability of $f$ is unaltered when any $m$ of its input bits are kept constant.

Using, Walsh transform below, the Boolean function $f$ is $m$-th order correlation immune if and only if ${\widehat {f}}(u)=0$, for all $u\in \mathbb {F} _{2}^{n}$, s.t. $1\leq w_{H}(u)\leq m,$, where $w_{H}(u)$ is the Hamming weight of $u$.

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 $m$-th order correlation-immune, then there exist a correlation between the output of the function and $m$ coordinated of its input. Moreover, if $m$ 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 $m$-th order correlation-immune functions are called $m$-resilient functions.

Using, Walsh transform below, the Boolean function $f$ is $m$-resilient if and only if ${\widehat {f}}(u)=0$, for all $u\in \mathbb {F} _{2}^{n}$, s.t. $w_{H}(u)\leq m,$.

The maximum value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m } such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m } -resilient is called the resiliency order of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} .

Walsh transform

Correlation immunity and resiliency can be characterized through the Walsh transform of the Boolean function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f } .

The discrete Fourier transform of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f } is by definition the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \widehat{f} } defined by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \widehat{f}(u)=\sum_{x \in F_2^n} f(x)(-1)^{u \cdot x} \text{ for all } u \in \mathbb{F}_2^n,}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u \cdot x } is inner product Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u \cdot x = u_1x_1 \oplus \dots \oplus u_n x_n } . The Walsh transform of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f } is the discrete Fourier transform of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \chi_f = (-1)^f } , i.e Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall u \in \mathbb{F}_2^n }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \widehat{\chi_f}(u)=\sum_{x \in \mathbb{F}_2^n}(-1)^{f(x) \oplus x \cdot u}.}

Example

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r } be a positive integer smaller than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } . Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g } be any Boolean function on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2^{n-r} } and let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi } be a mapping, s.t. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi : \mathbb{F}_2^{n-r} \mapsto \mathbb{F}_2^{r} } . Define the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{\phi , g}(x, y) } for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \mathbb{F}_2^r, \; y \in \mathbb{F}_2^{n-r} } , s.t.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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), }

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_i(y) } is the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i } -th coordinate of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(y) } . Then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{\phi , g}(x, y) } is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m } -resilient with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \geq k } if every element in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(\mathbb{F}_2^{n-r}) } has Hamming weight strictly greater than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k } .