# How many $S$-Boxes of length $3$ are there over $\mathbb{F}_{2}$?

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$$?

• What are the requirements of an S box? May 21 at 0:12
• 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?
– fgrieu
May 22 at 7:36

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

• 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.
– fgrieu
May 22 at 8:16