Score:1

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

sa flag

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

Wilson avatar
se flag
What are the requirements of an S box?
fgrieu avatar
ng flag
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](https://crypto.stackexchange.com/a/42471/555) Avalanche Criterion?
Score:2
sa flag

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

fgrieu avatar
ng flag
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.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.