I am working on AES S_box and trying to find out its properties like Correlation Immunity, Balancedness, Algebraic Degree, ANF form etc.

These Papers 1, 2 give a nice definitions to above said terms.

Also this very famous paper by T. Siegenthaler proved a fundamental relation between the number of variables 'n', algebraic degree 'd' and order of correlation immunity 'm' of a Boolean function : $$m+d <= n$$

Moreover, if the function is balanced then $$m+ d <= n − 1$$

I used this python script to find the ANF form and the Algebraic Degree comes out to be 7 i.e d=7 and we know for AES S_box n equals to 8 and its balanced function.

So putting all this data in that formula gives m=0 i.e. order of correlation immunity be zero.

Is this the right Correlation Immunity? or I am doing something wrong. Those who have worked in this field kindly help.


The Siegenthaler result is for boolean functions, i.e., $f:F_2^n\rightarrow F_2$, while you are considering vectorial boolean functions $$f:F_2^n\rightarrow F_2^n$$ so you can't apply it. The results in this area are quite technical. Some overview:

  1. You could certainly compute resilience (hence correlation immmunity for AES Sbox) by using the definition that the resilience of a vectorial boolean function $$S:F_2^n\rightarrow F_2^n$$ is the minimum resilience of the boolean functions as $b$ ranges over the nonzero vectors in $F_2^n.$ So $$\min\{ \rho(b\cdot S(x)): b \in {F_2^n},b\neq \mathbf{0}\},$$ where $\rho(\cdot)$ denotes resilience of a boolean function. So you need to check $255$ boolean functions, since $n=8.$

  2. There are some constructions in this area, I suggest you look at the draft of a chapter by Claude Carlet on vectorial boolean functions (especially the last section) available at his homepage. You may also find his chapter on boolean functions interesting, in terms of more basic definitions.

Edit: To clarify 1, let the output bits be $S_i(x)$ for $i=1,\ldots,8.$ Compute the correlation immunity of each nonzero bitwise linear combination of these functions, such as those of weight 1: $$S_1(x),S_2(x),\ldots,S_8(x),$$ weight 2: $$S_1(x)+S_2(x),S_1(x)+S_3(x),\ldots,S_7(x)+S_8(x),$$ up to weight 8. This will give you 255 functions. The minimum correlation immunity of this collection of 255 functions is the correlation immunity of the AES Sbox.

Finally the correlation immunity of a boolean function is equal to the largest hamming weight $w$ for which all hadamard coefficients $\hat{f}(\lambda)$ for $\lambda$ with weight $1,2,\ldots,w$ are all zero.

  • $\begingroup$ Thank You @kodlu i guess i mixed up some things and concluded a formula for wrong domain.The upper bound you gave is for Nonlinearity not for order of correlation immunity. I have been through that paper of Claude Carlet but couldn't grasp the math behind finding Correlation Immunity of Vector Boolean Function. I have deduced the Walsh Transform , don't know what furthur to do, Can you help me out? $\endgroup$ Jul 27 '16 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.