Calculate number of active S-boxes for a cipher where one word observes multiple times overlapped S-box substitution in a single encryption round

Question

There are many ways in which the number of active sboxes of a cipher for one round can be calculated. Like, a manual approach (all possible input differential are applied in the two plaintexts $P_0, P_1$ and then it is observed what is the least amount of nonzero S-box that the xor-sum of the cipher $C_0, C_1$ produces, after one round), then MILP and other approaches are also there.

Now, if there is a cipher in which the S-box substitution happens multiple times; in a single encryption round, a word gets substituted multiple times by an S-box. Most importantly the substitutions happen in an overlapped manner between the neighboring words.

Let, 128-bit the block length, that is arranged in a $8\times 16$ binary matrix. The S-box is a 8-bit randomly generated permutation. Now, in each row of the binary matrix 8-bit region (called the substitution window) is selected and replaced by the s-box. Next, the substitution window shift 2-bit to the left side of the row and a mixture of the 6-bit overlapped value and 2-bit new value that comes inside the substitution window selected for the next substitution. This substitution and shift continues till the substitution window reaches to the end of the row. Then the same operation happens starting from the right hand side till the substitution window reaches to the left end. In this cipher there is also a mechanism that diffuses each column of the binary matrix.

In such a system how can I calculate the number of active s-boxes?

Answer 1

MILP works on a bit level, so is still applicable. The only tricky part is to encode the DDT of the S-Box in MILP, there were a few papers on that, e.g.

"Efficient MILP modelings for Sboxes and Linear Layers of SPN ciphers", ToSC 2020.

An implementation is available too.