How can I calculate non-linearity of an s-box element wise?

Question

First i transform the s-box into row matrix like if i have 4×4 s-box having 16 elements into 1×16 row matix then substitute the binary values in column . multiply the matrix by mobius trasformation matrix then tell me how to trasform the s-box which is in binary form into decimal form? Also how i calculate the non linearity of certain element of that s-box.

Answer 1

I'm not sure if I fully understand your question.

• "tell me how to trasform the s-box which is in binary form into decimal form?": Changing numbers between binary and hexadecimal (or decimal, if you would really want to) is not different for numbers that are used with S-boxes compared to any other numbers.
• "Also how i calculate the non linearity of certain element of that s-box.": As far as I am aware, nonlinearity is defined for functions from $\mathbb{F}_2^n$ to $\mathbb{F}_2^m$. In the context of S-boxes, we typically consider the nonlinearity of a full S-box, and not of a single element.

Having said that, let $S : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^m$ be our S-box. Then the nonlinearity $\mathcal{N}$ of $S$ is usually defined in terms of the linearity $\mathcal{L}$ of $S$, which is usually defined in terms of the $bias$ $\mathcal{E}$ of Boolean functions. Here is the full definition, where $S_b$ considers Boolean component functions of $S$ and $\varphi_a$ does $x \mapsto ax$:

$\mathcal{N}(S) = 2^{n-1} - \frac{1}{2}\mathcal{L}(S) = 2^{n-1} - \frac{1}{2} \max_{a,b \in \mathbb{F}_2^{m*}} \left|\mathcal{E}(S_b + \varphi_a)\right|$.

In this answer, I elaborated on how to compute this bias $\mathcal{E}(S_b + \varphi_a)$ to compute the values in the linear approximation table of $S$, including a fully worked out example. I'll try to avoid repeating that here.

Once all values in the linear approximation table are computed, the largest absolute number (ignoring the trivial case of $a=b=0$) is called the linearity. Using the definition, it is then straightforward to calculate the nonlinearity.