Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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$?
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
