Can the S-Boxes and the P-Box commute?

Consider an SPN operating on blocks of size $m\ell$ bits. Suppose that each round consists of adding the round key (bitwise xor), applying $m$ S-boxes (so that each S-box operates on $\ell$ bits), and finally applying the P-box, that is, a fixed permutation of indices. To be more precise let $$S=(\{0,1\}^{\ell m},(S_{2^\ell})^m,\sigma),$$ $$T=(\{0,1\}^{\ell m},S_{\ell m},\pi_P)$$

be the concatenation of the S-boxes, and the P-box, respectively, when thought of as a cryptosystems.

We say that a cryptosystem $A=(P,K_1,e_1)$ can be embedded in the cryptosystem $B = (P,K_1,e_2)$ if there exists a map $\phi:K_1 \rightarrow K_2$ such that $e_1(x,k_1)=e_2(x,\phi(k_1))$ for all $x \in P,k_1 \in K_1$. We say that two cryptosystems are equivalent if they can be embedded into each other.

Why is it the case that the product cryptosystems $T \times S$ and $S \times T$ are not equivalent? In other words, why do they not commute?

It is easily seen that adding a round key commutes with the P-box. The possibility of interchanging the S-boxes and P-box would therefore threaten the whole security of the considered SPN.

I am interested in the proof that this is not so.

• It seems as though you are stating that symbol substitutions (S-Boxes) and positional permutations (P-Boxes) do not commute, when in fact they do. It is the addition of round keys that does not commute with S-Boxes. – N.jackoson Jan 30 '18 at 22:15