# Correlation Immunity Of 4 bit S Box

I have a 4 bit S Box

byte[] S = new byte[16] { 0x9, 0xE, 0x5, 0x6, 0xA, 0x2, 0x3, 0xC, 0xF, 0x0, 0x4, 0xD, 0x7, 0xB, 0x1, 0x8 };


How can i calculate Correlation Immunity of this S Box

• So does the Xbox map: 0x0 to 0x9, 0x1 to 0xE, ..., 0xF to 0x8? May 25 '16 at 9:47

A boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ has correlation immunity $k$ if its walsh-hadamard transform coefficients $$F(a)=\sum_{ x \in \{0,1\}^n} (-1)^{f(x)+a\cdot x}$$ are zero whenever $1\leq w(a)\leq k,$ where $w(a)$ is the hamming weight of $a$.
An sbox $S:\{0,1\}^n\rightarrow \{0,1\}^n$ has correlation immunity $k$ if the functions $b \cdot S(x)$ all have correlation immunity $k$ whenever $b$ is not the all zero vector.
Operationally this means that all nontrivial output linear combinations of the sbox are uncorrelated with all linear combinations of $\leq k$ of the input bits, raising the complexity of divide and conquer attacks in stream ciphers.
In block ciphers this means that any useful linear characteristic must have output weight at least $k+1$ provided we also require that the walsh-hadamard coefficients are zero when $a$ is zero, i.e., the relevant functions are $k-$resilient.
For you $n=4.$