View source for Correlation immunity and resiliency of Boolean functions

In the standard model of a stream cipher, the outputs of <math>n</math> 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 <ref>A. Canteaut, M. Trabbia, Improved fast correlation attacks using paritycheck equations of weight 4 and 5, Advanced in Cryptology-EUROCRYPT 2000. Lecture notes in computer science 1807 (2000), pp. 573-588.</ref>,<ref>T. Johansson, F. Jonsson ¨ , Improved fast correlation attack on stream ciphers via convolutional codes, Advances in Cryptology - EUROCRYPT’99, number 1592 in Lecture Notes in Computer Science (1999), pp. 347–362.</ref>,<ref>T. Johansson, F. Jonsson ¨ Fast correlation attacks based on turbo code techniques, Advances in Cryptology - CRYPTO’99, number 1666 in Lecture Notes in Computer Science (1999), pp. 181–197.</ref>,<ref>T. Siegenthaler, Decrypting a Class of Stream Ciphers Using Ciphertext Only, IEEE Transactions on Computer, V. C-34, No 1 (1985), pp. 81-85.</ref>. To resist these attacks the Boolean function must be properly chosen: balanceness, large algebraic degree, high nonlinearity, and high order correlation immunity <ref>Carlet, C. (2002). On the Coset Weight Divisibility and Nonlinearity of Resilient and Correlation-Immune Functions. In: Helleseth, T., Kumar, P.V., Yang, K. (eds) Sequences and their Applications. Discrete Mathematics and Theoretical Computer Science. Springer, London. <nowiki>https://doi.org/10.1007/978-1-4471-0673-9_9</nowiki></ref>. 

The Boolean functions used in the stream ciphers must be balanced for avoiding statistical dependence between their input and their output <ref>Carlet C. ''Boolean Functions for Cryptography and Coding Theory''. Cambridge University Press; 2021.</ref>. 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 <math>f</math> by an affine function makes fast correlation attacks feasible, see <ref>W. Meier, O. Staffelbach, Fast correlation attack on certain stream ciphers, Jounal of Cryptology (1989), pp. 159-176.</ref>. A fourth criterion on the combining function is that the distribution probability of its output should be unaltered when any <math>m</math> of its inputs are fixed, with m as large as possible. This property, called <math>m</math>-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 <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>.

In the 90’s, high-order resilient functions with the best possible algebraic degree and nonlinearity were needed for applications in stream ciphers using the combiner model. But fast algebraic attacks (FAA) have changed the situation. The combiner model is now considered as problematic, because of Siegenthaler’s bound and the fact that combiner or filter functions need to have very high algebraic degree for resisting FAA. 

== Correlation immunity ==

=== Definition ===
The Boolean function <math>f</math> is called <math>m</math>-th 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>-th 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 <ref>Siegenthaler, T. (1984). “Correlation-immunity of nonlinear combining functions for cryptographic applications.” IEEE Transactions on Information theory, IT-30 (5), 776–780.</ref>. 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>.

== Dependance between resiliency, nonlinearity and algebraic degree ==
'''Siegenthaler''' proved that an <math>n
</math> input 1 output, <math>m</math>-resilient (balanced <math>m</math>-th order correlation immune) Boolean function with algebraic degree <math>d</math> satisfies the '''inequality''' : <math>m + d \leq n − 1</math>.

Any <math>m
</math>-resilient function <math>f
</math> on <math>\mathbb{F}^n_2
</math> has nonlinearity smaller than or equal to <math>2^{n−1} − 2^{m+1}
</math> <ref>P. Sarkar, S. Maitra, Nonlinearity Bounds and Constructions of Resilient Boolean Functions, CRYPTO 2000, LNCS Vol. 1880, ed. Mihir Bellare, pp. 515-532 (2000).</ref>, and also independently obtained by <ref>Y. Tarannikov, On resilient Boolean functions with maximal possible nonlinearity, Cryptology ePrint archive (<nowiki>http://eprint.iacr.org/</nowiki>), Report 2000/005, 18 pp. (2000); and Proceedings of Indocrypt 2000, Springer Verlag, LNCS 1977 (2000) pp. 19-30.</ref>.

== Walsh transform ==
Correlation immunity and resiliency can be characterized through the Walsh transform of the Boolean function <math>f
</math><ref>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.</ref>.

The discrete Fourier transform of <math>f
</math> is by definition the function <math>\widehat{f}
</math> defined by

<math>\widehat{f}(u)=\sum_{x \in F_2^n} f(x)(-1)^{u \cdot x} \text{ for all } u \in \mathbb{F}_2^n,</math>

where <math>u \cdot x
</math>  is inner product <math>u \cdot x = u_1x_1 \oplus \dots \oplus u_n x_n
</math>. The Walsh transform of <math>f
</math> is the discrete Fourier transform of <math>\chi_f = (-1)^f
</math>, i.e <math>\forall u \in \mathbb{F}_2^n
</math> 

<math>\widehat{\chi_f}(u)=\sum_{x \in \mathbb{F}_2^n}(-1)^{f(x) \oplus x \cdot u}.</math>

== Example ==
Let <math>r
</math> be a positive integer smaller than <math>n
</math>. Let <math>g
</math> be any Boolean function on <math>\mathbb{F}_2^{n-r}
</math> and let <math>\phi
</math> be a mapping, s.t. <math>\phi : \mathbb{F}_2^{n-r} \mapsto \mathbb{F}_2^{r} 
</math>. Define the function <math>f_{\phi , g}(x, y)
</math> for <math>x \in \mathbb{F}_2^r, \; y \in \mathbb{F}_2^{n-r}
</math>, s.t.

<math>f_{\phi , g}(x, y)=x \cdot \phi(y) \oplus g(y)=\bigoplus_{i=1}^r x_i \phi_i(y) \oplus g(y),
</math>

where <math>\phi_i(y)
</math> is the <math>i
</math>-th coordinate of <math>\phi(y)
</math>. Then <math>f_{\phi , g}(x, y)
</math> is <math>m
</math>-resilient with <math>m \geq k
</math> if every element in <math>\phi(\mathbb{F}_2^{n-r})
</math> has Hamming weight strictly greater than <math>k
</math> <ref>Carlet, C. (2005). Correlation Immune and Resilient Boolean Functions. In: van Tilborg, H.C.A. (eds) Encyclopedia of Cryptography and Security. Springer, Boston, MA . <nowiki>https://doi.org/10.1007/0-387-23483-7_81</nowiki></ref>.

== References ==
<references />