1
$\begingroup$

Is there a simple way if counting the number of $S$-Boxes of length $\ell$ over $\mathbb{F}_{2}$? By $S$-box I mean an $S$-box satisfying the avalanche condition.

I mean it is quite easy to see that for $\ell=2$ the answer is $0$ but I want to know if there is a general formula, specifically for $\ell=3$?

$\endgroup$
2
  • 2
    $\begingroup$ What are the requirements of an S box? $\endgroup$
    – Wilson
    May 21, 2023 at 0:12
  • $\begingroup$ I don't get the question. It states "for $\ell=2$ the answer is $0$"; but isn't $S(x_0,x_1)=x_0\mathbin|x_1$ "satisfying the avalanche condition" and even the Strict Avalanche Criterion? $\endgroup$
    – fgrieu
    May 22, 2023 at 7:36

1 Answer 1

2
$\begingroup$

By definition, an S-box usually assumed to be one-to-one. From your question, you want it to be a fixed bitlength, say $n.$ So it is a one to one mapping from $\{0,1\}^n$ to itself, i.e., a permutation on $2^n$ point. This is usually referred to as an $n\times n$ S-box. There are $2^n!$ such mappings. You can use Stirling's formula or compute this for small $n.$

For example $$2^3!=2^3(2^3-1)\cdots 2\cdot 1=40320.$$

The question becomes more interesting and quite complex if we consider some S-boxes to be equivalent from a cryptographic point of view. For example let our S-box input be $(x_1,x_2,x_3)$ and output be $(y_1,y_2,y_3).$ One could argue that relabeling these gives you the same S-box. It gets quite complicated once we start thinking of counting distinct S-boxes under other equivalences.

Thinking of linear cryptanalysis for example, one might say, all $n\times n$ S-boxes which behave the same under analysis given by pre- and post-multiplication by non-singular $n\times n$ matrices and addition of constants at input and output are equivalent.

A nice paper addressing a lot of this is Saarinen, Cryptographic analysis of all $4\times 4$ S-boxes available here

$\endgroup$
1
  • 1
    $\begingroup$ I doubt the question is about one-to-one S-boxes, for it (now) states "satisfying the avalanche condition". I still find no way to read the question such that "for $\ell=2$ the answer is $0$" is correct. $\endgroup$
    – fgrieu
    May 22, 2023 at 8:16

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.