2
$\begingroup$

I want to calculate the hamming weight of a S-Box using this formula: $\text{hw}(f) = \sum_{x=0}^{2^n-1} f(x)$. Where $f: \{0, 1\}^n \rightarrow \{0, 1\}$

My problem is that I don't know how to get the $f$-function.

I found that helpful paper: THE DESIGN OF S-BOXES. At Page 9 (18) boolean functions are described. But she only prints the truth table (Table 2.1) without describing her $f$-function. She only says $f$ is a linear function, therefore I think $f$ depends on my S-Box?

For example, if I have this $2 \times 2$ S-Box:

0    1    2    3 
1    3    0    2 

$00 \rightarrow 01\\ 01 \rightarrow 11\\ 10 \rightarrow 00\\ 11 \rightarrow 10$

What are the $f$-functions and what is the hamming weight?

$\endgroup$
2
  • $\begingroup$ The link you shared does not exist $\endgroup$
    – hola
    Jul 21, 2020 at 17:13
  • 1
    $\begingroup$ @hola you could use the Wayback Machine - Internet Archive to find the original document. $\endgroup$ Feb 15, 2023 at 10:04

2 Answers 2

4
$\begingroup$

To know how many boolean functions you got you have to look at the output of the S-Box...

A $N \times M$ S-Box gives you $M$ functions. In the example you passed, you have a function $f_1$ given by

$00 \rightarrow 0\\ 01 \rightarrow 1\\ 10 \rightarrow 0\\ 11 \rightarrow 1$

and a function $f_2$ given by

$00 \rightarrow 1\\ 01 \rightarrow 1\\ 10 \rightarrow 0\\ 11 \rightarrow 0$

So, the concatenation of $f_1(x)$ with $f_2(x)$ gives you the output of the S-box.

The Hamming Weight of $f_1$, which is simply the number of ones in the output of that function, is $hw(f_1) = 2$. And the same is valid for $f_2$, which means $hw(f_2) = 2$.

$\endgroup$
6
$\begingroup$

Your n x n S-Box can be seen as a set of $ n $ boolean vectors of size $ n $. Actually you have got $ n $ functions, each one is the truth table of one particular vector (or column). In your example there are 2 columns thus 2 functions. For each column the number of 1's is 2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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