Mathematical structure for Sbox

Question

Recently, when I studied the permutation cipher, I saw a matrices structure which is same as permutation cipher. This method was so simple and interesting for me.

Let $m$ be $n$-bit plain text and $P=[p_1,...,p_n]$ be the permutation secret key such that $P(m_i)=m_{p_i}$.

For example, let $m=5={(101)}_2$ and $P=[2,1,3]$. So $P(5)={(011)}_2=3$. In mathematical points of view, we can do this method with matrices multiplication as fallow:

$P(m)=\left(\begin{array}{ccc}m_1&m_2&m_3\end{array}\right)\cdot\left(\begin{array}{ccc}0&1&0\\1&0&0\\0&0&1\end{array}\right)=\left(\begin{array}{ccc}m_2&m_1&m_3\end{array}\right).$

In general case, instead of using $P$ as $1\times n$ vector, we can use $n\times n$ matrices with $0,1$ elements, such that there exist only one $1$ in each column( in the position $p_i$).

This equivalent presentation make analysis and attacks so easier. Is there exist similar mathematical method for substitution cipher?

Answer 1

Well, at least two representations come to my mind, but I'm afraid you will not find them too useful. In general, S-boxes are designed with the goal in mind that such "mathematical" representations do not help in exposing any more structure than just writing down the table does.

• If we are talking about bit strings, i.e., an S-box $S\colon\{0,1\}^n\to\{0,1\}^n$, we can interpret $\{0,1\}^n$ as a finite field $\mathbb F_{2^n}$. Over any field, polynomial interpolation works, thus there exists a unique polynomial of degree at most $2^n$ over $\mathbb F_{2^n}$ that describes the substitution $S$.
• Similarly to your permutation matrix example, any map $f\colon A\to B$ of finite sets can be written as a matrix: Let $A=\{a_1,\dots,a_n\}$ and $B=\{b_1,\dots,b_m\}$ (note this fixes an order on the sets), and define $F$ to be the binary $m\times n$ matrix which has $1$ in the entry labelled $i,j$ and only if $f(a_i)=b_j$. Then $F$ applied to the $i$th unit vector gives back the $j$th unit vector, where $b_j=f(a_i)$.

Note how both representations have size exponential in the bit length of the input.