1 Introduction

Nowadays, huge amounts of information are transmitted in networks which is why information security is a subject that should be paid utmost attention to. To have confidentiality       as one of the main aspects of security, encryption is utilized. Encryption algorithms       can be divided into symmetric key and public key. Block cipher is one of the most       important types of symmetric key algorithms. Modern block ciphers consists of       several rounds. In each round input should be confused and diffused for which       substitution and permutation (diffusion) layers are used, respectively. The       substitution layer is often implemented using several small non-linear substitution       boxes (S-boxes) and the diffusion layer combines the output of each S-box.

To represent diffusion layers, an n × n matrix is used where n is the number of S-boxes in each round. Generally, the matrix can be over finite fields, and in the simplest case, n × n matrix       can be over GF (2) (binary matrix). The E2 [1] and the Camellia block ciphers [2] use 8 × 8 binary matrices with the branch number of 5 while ARIA [3] uses an involutory 16 ×16 binary matrix with the branch number of 8 as a diffusion layer. Also, Skinny [4] and Midori [5] are the block ciphers using binary matrices with good properties to implement in hardware. In [6] a 32 × 32 bi-nary matrix with the branch number 10 was proposed. Some 24 × 24 binary matrices are introduced in [7] with good implementation properties for lightweight block ciphers.

If the diffusion layer has good properties, then many S-boxes will be active after a       few rounds which is why the diffusion layer design has a deep impact on the resistance       of block ciphers against linear [8] and differential cryptanalysis [9].

In this paper, to investigate the diffusion properties of proposed binary matrices, we employ them as the diffusion layer of the SPN structure shown in Fig. 1.       This structure uses n S-boxes of length m bits. So, the diffusion layer of the considered SPNs is n × n binary matrices.

Figure 1.One round of SPN structure with the binary diffusion layer

We use the following definitions in this paper.

Definition 1. For any given ∆x, ∆y, Γx, Γy ∈ $Z_2^m$, the differential and linear probabilities of S-box S, are defined as:

$\begin{array}{cc}\mathrm{DP}(\mathrm{∆x}\to \mathrm{∆y})=\frac{\#\{x\in Z_2^m|s\left(x\right)⨁s(x⨁\mathrm{∆x})=\mathrm{∆y}\}}{2^m}& \mathrm{(1)}\end{array}$

$\begin{array}{cc}\mathrm{LP}(\mathrm{\Gamma x}\to \mathrm{\Gamma y})={(2\times \frac{\#\{x\in Z_2^m|x.\mathrm{\Gamma x}=s\left(x\right).\mathrm{\Gamma y}\}}{2^m}\_1)}^2& \mathrm{(2)}\end{array}$

where a.b denotes the parity of the bit-wise product of a and b.

Definition 2. The maximum differential and linear probabilities of an S-box are defined as:

$\begin{array}{cc}p=\underset{\mathrm{∆x}\ne 0,\mathrm{∆y}}{\max }\mathrm{DP}(\mathrm{∆x}\to \mathrm{∆y})& \mathrm{(3)}\end{array}$

$\begin{array}{cc}q=\underset{\mathrm{\Gamma x},\mathrm{\Gamma y}\ne 0}{\max }\mathrm{LP}(\mathrm{\Gamma x}\to \mathrm{\Gamma y})& \mathrm{(4)}\end{array}$

Definition 3. An S-box is a differential (resp. linear) active S-box if the input difference (resp. output mask) value of the S-box is nonzero.

For a linear diffusion layer which can be represented by a matrix multiplication y = A.x, it can be shown that the output difference (∆y) is obtained from the input difference (∆x) by ∆y = A. ∆ x:

$\begin{array}{cc}{y}_1=A.x_1,y_2=A.x_2\Rightarrow \mathrm{∆y}=A.\mathrm{∆x}& \mathrm{(5)}\end{array}$

Also, the input linear mask (Γ_x) is obtained from the the output linear mask (Γ_y) by       (Γ_x)= A^tΓ_y where A^t denotes the transpose of matrix A:

$\begin{array}{cc}y=A.x\Rightarrow {\Gamma }_y^t.y={\Gamma }_y^t.A.x={(A^t.{\Gamma }_y)}^t.x\Rightarrow {\Gamma }_x=A^t{\Gamma }_y& \mathrm{(6)}\end{array}$

Definition 4. The minimum number of differential active S-boxes of two rounds of a linear diffusion layer D is called the differential branch number and is defined as [10]:

$\begin{array}{cc}{\beta }_d\left(D\right)=\underset{x\ne 0}{\min }\left\{w\right(x)+w(D\left(x\right)\left)\right\}& \mathrm{(7)}\end{array}$

where w(x) is the number of non-zero elements in vector x.

From relations (5) and (6), we can conclude that for a block cipher with matrix A       as its diffusion layer, the minimum number of linear active S-boxes (MNLAS) is equivalent       to the minimum number of differential active S-boxes (MNDAS) of that block cipher with matrix A^t as diffusion layer.

Notations

In this paper, to avoid the representation of large matrices, some notations are introduced as follows:

Definition 5. z_n×m shows an all-zeros n×m matrix.  For example:

$\begin{array}{cc}{z}_{\mathrm{n\times m}}=\left(\begin{array}{ccc}0& 0& 0\\ 0& 0& 0\end{array}\right)& \mathrm{(8)}\end{array}$

Definition 6.P_{i0 ,i1 ,i2 ,i3} represents a 4 × 4 binary matrix with one 0 in each row where i_j (i_j ∈ 0, 1, 2, 3) shows the position of zero elements in the j^th row. For example:

$\begin{array}{cc}{P}_{\mathrm{3,1,2,0}}=\left(\begin{array}{cccc}1& 1& 1& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 0& 1& 1& 1\end{array}\right)& \mathrm{(9)}\end{array}$

Definition 7.${\prod }_{\left(i_0,i_1,\mathrm{...},i_{\mathrm{n-1}}\right)}^n$ represents an n × n binary matrix with one 1 in each row where i_j (i_j ∈ 0, 1,... , n − 1) shows the position of non-zero element in the j^th row. For example:

$\begin{array}{cc}{\prod }_{\left(0,5,4,7,2,1,6,3\right)}^8=\left(\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 0\end{array}\right)& \mathrm{(10)}\end{array}$

Our Contribution

Counting the number of (linear or differential) active S-boxes of consecutive rounds of an SPN is       often done by considering the truncated values for the block state. It means each all-zero or non-zero       S-box input and output is shown by one bit 0 or 1, respectively. Thus, the block state is shown       by an n-bit vector instead of an nm-bit value. In [11] a counting method was proposed that can be used to compute active S-boxes for several rounds of Rijndael. The complexity of this method linearly increases with the rise in the number of rounds.

It is proved that the ratio of MNDAS and MN-LAS to number of rounds for binary matrices proposed in [3] never exceeds Br/2 where Br is the matrix branch number. Then some 16 × 16 binary matrices will be proposed for which the mentioned ratio ex-ceeds Br/2 with an increase in number of rounds. For the new matrices MNDAS for R rounds (e.g. R = 40) will be determined using the method mentioned in [11]. To find MNLAS, the method is applied to At instead of A. The proposed matrices have the largest value of MNDAS and MNLAS among existing binary matrices for R > 5 rounds.

The mentioned method cannot be used for 32 × 32 binary matrices because of the method running time and the limitation of the used memory. Thus, some limitations have been       applied to the matrices of the mentioned size and the counting method has been modified.       In this paper, a new 32 × 32 binary matrix is also proposed. 8 rounds of an SPN structure       using the new matrix as the diffusion layer has at least 48 (linear or differential)       active S-boxes. The counting method can be extended for a new 32 × 32 non-binary matrix       which results in at least 60 (linear or differential) active S-boxes after 8 rounds. All of the proposed 16 × 16 and 32 × 32 matrices can be efficiently implemented.

The rest of this paper is organized as follows. In Section 2, the counting method mentioned in [11] with some slight changes are explained. Using this method, in Section 2, some 16 × 16 binary matrices are offered for which the MNDAS of several rounds are determined. In Section 3, a 32 × 32 binary matrix with at least 48 active S-boxes for 8 rounds and also a 32 × 32 non-binary matrix with at least 60 active S- boxes for 8 rounds will be proposed and the conclusion is in the last section.

2 New Binary Matrices

In this section, some new 16 × 16 binary matrices are proposed which provide the following properties when used as the diffusion layer in the SPN structure:

− The active S-boxes for R rounds of the proposed SPNs is large.

− The SPN can be efficiently implemented. According to the mentioned method, to compute the MNDAS for R rounds of the SPN structure using the new matrices, array T must be of size R × 2¹⁶.

The main idea to propose a new 16 × 16 matrix is the usage of the AES structure whose MDS matrix is replaced by binary matrices. By using the mentioned method, we observed       that the MNDAS and MNLAS for 4r rounds are greater than the expected value which is 16r. The first proposed matrix is as follows:

$\begin{array}{cc}{A}_1=\left(\begin{array}{cccccccccccccccc}1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 1& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 1& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 1& 0& 0& 0\end{array}\right)& \mathrm{(11)}\end{array}$

This matrix is the result of multiplying  ${\Pi }_{\mathrm{0,5,10,15,4,9,14,3,8,13,2,7,12,1,6,11}}^{\mathrm{16}}$   by Q1, where Q1 is given below.

$\begin{array}{cc}\mathrm{Q1}=\left(\begin{array}{cccc}{P}_{\mathrm{3,1,0,2}}& z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}\\ z_{\mathrm{4\times 4}}& P_{\mathrm{0,2,3,1}}& z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}\\ z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}& P_{\mathrm{1,3,2,0}}& z_{\mathrm{4\times 4}}\\ z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}& P_{\mathrm{2,3,0,1}}\end{array}\right)& \mathrm{(12)}\end{array}$

The differential branch number of A₁ is 4. The MNDAS of r rounds of the SPN structure using A₁ as the diffusion layer has been shown in Table 1. It can be observed from Table 1       that when the number of rounds increases, the ratio of the MNDAS to the number of rounds,       also increases. Although there are other options for matrices Q and Π, the results for the mentioned one are the best.

To investigate the security of the SPN cipher with A₁ as the diffusion layer against the impossible differential attack, we checked the length of impossible differentials.       We looked for truncated differentials of probability 1 in both encryption and decryption       directions and found out that after four rounds there is no byte whose difference       is zero and there is no set of bytes that the XOR of their differences is zero with       probability 1. This ensures us that this SPN does not have any impossible differential       in more than 6 rounds. In other words, we found a 6-round impossible differential for the SPN that uses A₁.

It should be noted that the A1 matrix is better than the Skinny matrix in terms of the active S-boxes and the resistance to impossible differential attack, but in terms       of hardware implementation in Skinny, 12 XOR operations are needed forthe diffusion       layer but for A1 this value requires 32 XOR operations (28 operations with an auxiliary variable).       Due to the fact that in order to compare the implementation of two block ciphers, it is necessary       to compare the number of rounds of the algorithm as well as the designed S-box, it is not possible       to have a detailed review between these diffusion layers of block ciphers in this paper.

To find a binary matrix with at a most 4-round impossible differential, we searched all permutation Π, but for all of them, there are impossible differentials on 5 or more rounds.       To overcome this problem, another matrix, A₂, is proposed which is the result of multiplying       Q2 by Π = ${\Pi }_{\mathrm{2,7,8,14,3,4,9,15,0,5,10,12,1,6,11,13}}^{\mathrm{16}}$ the form: , where Q2 is of

$\begin{array}{cc}\mathrm{Q2}=\left(\begin{array}{cccc}{P}_{\mathrm{3,0,1,2}}& P_{\mathrm{0,1,2,3}}& z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}\\ P_{\mathrm{3,0,1,2}}⨁P_{\mathrm{0,1,2,3}}& P_{\mathrm{0,1,2,3}}& z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}\\ z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}& P_{\mathrm{1,2,3,0}}& P_{\mathrm{1,2,3,0}}\\ z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}& P_{\mathrm{1,2,3,0}}⨁P_{\mathrm{2,3,0,1}}& P_{\mathrm{2,3,0,1}}\end{array}\right)& \mathrm{(13)}\end{array}$

The form of the upper left 8 × 8 sub-block of Q2 is like the matrix used in the Camellia block cipher.

The matrix A₂ = Q2 × Π has at most 4-round impossible differential distinguisher.

The MNDAS of r rounds of the SPN structure using A₂ as the diffusion layer has been shown in Table 2. The inverse of matrix Q2 can be efficiently implemented similar to the implementation       of matrix Q2. Software implementation of this matrix has been described in Appendix 1.

3 The Matrix

The method proposed in Section 2 cannot be directly used for 32 × 32 binary matrices       to determine the MNDAS of r rounds because of the large running time of the algorithm for each round.

Thus, a new method is used to determine a lower bound for the active S-boxes of r rounds of an SPN structure which uses a 32 ×32 binary matrix as its diffusion layer. This method is       different from the method described in Section 2 in the following aspects:

(1) Here, two m-bit sub-blocks (instead of one m-bit sub-block) are truncated to one bit.       Thus, the number of columns of the array T will be $2^{\frac{n}{2}}$

(2) In each iteration of the search algorithm two rounds will be analyzed (instead of one round in each iteration). Thus the array T will be of size $\frac{r}{2}\times 2^{\frac{n}{2}}$ (instead of r × 2ⁿ).

In the following, we introduce a new 32 × 32 binary matrix with suitable linear and differential properties. Consider the following 32 × 32 binary matrix A₃ = P.Π, where:

$\begin{array}{cc}P=\left(\begin{array}{c}{B}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}\\ z_{\mathrm{4\times 4}}{B}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}\\ z_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{B}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}\\ z_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{B}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}\\ z_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{B}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}\\ z_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{B}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}\\ z_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{B}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}\\ z_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{z}_{\mathrm{4\times 4}}{B}_{\mathrm{4\times 4}}\end{array}\right)& \mathrm{(14)}\end{array}$

and

$\begin{array}{cc}\Pi ={\Pi }_I^{\mathrm{32}}& \mathrm{(15)}\end{array}$

where

$I=\left\{0,1,7,8,9,\mathrm{14},\mathrm{15},\mathrm{16},\mathrm{17},\mathrm{22},\mathrm{23},\mathrm{24},\mathrm{25},\mathrm{30},\mathrm{31},4,5,2,3,\mathrm{12},\mathrm{13},\mathrm{10},\mathrm{11},\mathrm{20},\mathrm{21},\mathrm{18},\mathrm{19},\mathrm{28},\mathrm{29},\mathrm{26},\mathrm{27}\right\}$

The matrix Π is similar to the matrix representation of permutation P₄ introduced in [12 ]. B_4×4 is a 4*4 binary matrix as follows:

$\begin{array}{cc}B=P_{\mathrm{1,2,3,0}}=\left(\begin{array}{cccc}1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 0\\ 0& 1& 1& 1\end{array}\right)& \mathrm{(16)}\end{array}$

The sequence of transformations applied to the input of an SPN structure (regardless of the key addition) can be written as

$\begin{array}{cc}\mathrm{...}\circ P\circ \Pi \circ S\circ P\circ \Pi \circ S\circ P\circ \Pi S\circ P\circ \Pi \circ S& \mathrm{(17)}\end{array}$

Concerning commutativity of Π and S, this sequence can be rewritten as:

$\begin{array}{cc}\mathrm{...}\circ \Pi \circ P\circ \Pi \circ S\circ P\circ S\circ \Pi \circ P\circ \Pi \circ S\circ P\circ S\circ \Pi & \mathrm{(18)}\end{array}$

Fig 2 shows the SPN structure corresponding to the relation (18) which is composed of two different types of rounds S ∘ P ∘ S and Π ∘ P ∘ Π applied alternately. The input to the r^th sub-cipher       S ∘ P ∘ S is shown by $\left(I_0^r,I_1^r,\mathrm{...},I_{\mathrm{31}}^r\right)$, while the input to the r^th sub-cipher Π ∘ P ∘ Π is represented by $\left(O_0^r,O_1^r,\mathrm{...},O_{\mathrm{31}}^r\right)$

In Section 2, the truncated value of $I_i^{\mathrm{r,t}}$ was represented by Iiwhich could be 0 or 1. Now the double-truncated value for every pair $\left(I_{\mathrm{2i}}^r,I_{\mathrm{2i+1}}^r\right)$, i= 0, 1,... , 15 is shown by ${\bar{I}}_i^{\mathrm{r,t}}$ which can be $\bar{0}$  or $\bar{1}$. . If both of $I_{\mathrm{2i}}^r$ and $I_{\mathrm{2i+1}}^r$ are all-zero, ${\stackrel{\_}{I}}_i^{\mathrm{r,t}}$ will be shown by $\bar{0}$.       In other cases, it will be shown by $\bar{1}$. $\left(I_0^r,I_1^r,\mathrm{...},I_{\mathrm{31}}^r\right)$       can       be shown with the doubletruncated vector $\left({\stackrel{\_}{I}}_0^{\mathrm{r,t}},{\stackrel{\_}{I}}_1^{\mathrm{r,t}},\mathrm{...},{\stackrel{\_}{I}}_{\mathrm{15}}^{\mathrm{r,t}}\right)$ which corresponds to the double-truncated value ${\sum }_{\mathrm{i=0}}^{\mathrm{i=15}}{\stackrel{\_}{I}}_i^{\mathrm{r,t}}.2^i$. This double-truncated       value is a number between 0 and 65535. Similar notation can be used for the input to the ith application of Π∘ P ∘Π.

Applying the S-box layer (S) to a double-truncated vector does not change its value, i.e., the Stransformation is considered an identity transformation on a double-truncated vector.       As can be seen from Fig. 2 the Π is equivalent to a permutation on 16 2m-bite values.       Therefore Π acts as a permutation on 16 elements of a double truncated vector.       This transformation is one-to-one. The application of P is realized by a parallel       application of 8 B functions. Double- truncated input to a B can be shown by       $\left(\stackrel{\_}{0},\stackrel{\_}{0}\right),\left(\stackrel{\_}{0},\stackrel{\_}{1}\right),\left(\stackrel{\_}{1},\stackrel{\_}{0}\right)\mathrm{or}\left(\stackrel{\_}{1},\stackrel{\_}{1}\right)$. Applying B to $\left(\stackrel{\_}{0},\stackrel{\_}{1}\right)$ and $\left(\stackrel{\_}{1},\stackrel{\_}{0}\right)$ results in $\left(\stackrel{\_}{1},\stackrel{\_}{1}\right)$.       Applying B to $\left(\stackrel{\_}{1},\stackrel{\_}{1}\right)$ results in $\left(\right(\stackrel{\_}{0},\stackrel{\_}{1}\left),\right(\stackrel{\_}{1},\stackrel{\_}{0}\left)\mathrm{or}\right(\stackrel{\_}{1},\stackrel{\_}{1})$. A function B is called active       if its input (or output) is not all zero. Each active B in the application of S ∘ P ∘ S makes       at least 4 S-boxes active in its input and its output.

Figure 2.Equivalent form of four rounds of the SPN with A3 as the diffusion layer

Based on Fig. 2, the analysis of the mentioned structure is as follows. To find a lower        bound for MNDAS of R rounds of the mentioned SPN, all of the double-truncated values for       the input of the SPN shown in Fig. 2 and all of the possible transitions by application of       the P layers will be considered. In the considered paths, each active B in S ∘ P ∘ S sequence       of functions, adds four active S-boxes to the lower bound of MNDAS.

Considering a double-truncated vector for the first application of S ∘ P ∘ S, the number of       paths is exponentially increased by adding each P layer in the sequence of applied functions.       To overcome this problem, an array T of the size $\frac{R}{2}\times 2^{\mathrm{16}}$ is built. The numbering to the rows       and the columns of the array starts  from 1 and 0, respectively. T[i][j] shows the MNDAS of the characteristics which finished with the doubletruncated value j (a number from 0 to 65535) at the end of the i^th application of Π∘P∘Π. Computation of i + 1^th row of T is performed by using the i^th row of T. T[r + 1][j] is computed using the exhaustive search over T[r][i], i = 0,... , 65535 and all of the possible transitions from ${\stackrel{\_}{I}}^{\mathrm{r+1,t}}=i$ to $O^{\mathrm{r+1,t}}=k$, k = 0, 1,... , 65535 by i + 1^th application of the S ∘ P ∘ S and all of the possible transitions from ${\stackrel{\_}{I}}^{\mathrm{r+1,t}}=i$ to $O^{\mathrm{r+1,t}}=k$ to ${\stackrel{\_}{I}}^{\mathrm{r+1,t}}=i$ to $I^{\mathrm{r+2,t}}=j$ by i + 1^th application of the Π∘ P ∘Π. For each active B in the i + 1^th application of the S∘P∘S, 4 is added to the lower bound of the number of active S-boxes of the characteristic. Thus we have

$\begin{array}{cc}T[r+1]\left[j\right]=\underset{\mathrm{i,k}}{\min }\left\{T\right[r\left]\right[i]+4\times l|{\stackrel{\_}{I}}^{\mathrm{r+1,t}}=i\to {\stackrel{\_}{I}}^{\mathrm{r+2,t}}=j\mathrm{is\; possibleand}{\stackrel{\_}{I}}^{\mathrm{r+1,t}}\mathrm{makes\; l\; different}\mathrm{Bs}\mathrm{active}\}& \mathrm{(19)}\end{array}$

For the mentioned structure the minimum non-zero values of the 4^th row of the T array is 48 which means that 8 rounds of the structure have at least 48 active S-boxes.

Table 3 and Table 4 show the possible transitions from ${\stackrel{\_}{I}}^{\mathrm{r,t}}$ to ${\stackrel{\_}{O}}^{\mathrm{r,t}}$ and ${\stackrel{\_}{O}}^{\mathrm{r,t}}$ to ${\stackrel{\_}{I}}^{\mathrm{r+1,t}}$, respectively.

Example 1. For computing T[r+1][153] it can be seen from Table 4 that one of the possible values for ${\stackrel{\_}{O}}^{\mathrm{r+1,t}}$ which results in ${\stackrel{\_}{I}}^{\mathrm{r+2,t}}=\mathrm{153}$ is 3. From Table 3 it is concluded that 1,2 and 3 are some values for ${\stackrel{\_}{I}}^{\mathrm{r+1,t}}$ which can be transformed to ${\stackrel{\_}{O}}^{\mathrm{r+1,t}}=3$. So minimum of T[r][1] + 1 × 4, T[r][2] + 1 × 4 and T[r][3] + 1 × 4 can be a candidate for T[r+1][153]. Considering all of the possible transformations results in the final value of T[r+1][153].

The most important properties of B which affect the resultant bound are as follows:

(1) The minimum active sub-blocks in the input and output of B takes its maximum possible value.

(2) Double-truncated pairs $\left(\stackrel{\_}{0},\stackrel{\_}{1}\right)$ and $\left(\stackrel{\_}{1},\stackrel{\_}{0}\right)$ results in $\left(\stackrel{\_}{1},\stackrel{\_}{1}\right)$

To see the effect of the second property on the overall diffusion of the SPN, consider the following matrix B₁:

$\begin{array}{cc}{B}_1=\left(\begin{array}{cccc}1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 0\\ 0& 1& 1& 1\end{array}\right)& \mathrm{(20)}\end{array}$

The minimum positive active sub-blocks in the input and output of B₁ and B are the same, but if B₁ is used instead of B in the SPN mentioned in this section, the obtained lower bound       of MNDAS for 8 rounds of the SPN would be 16, which is much smaller than the lower bound       for SPN using B. This egregious difference is the result of the possible transformations       of $\left(\stackrel{\_}{0},\stackrel{\_}{1}\right)$ to $\left(\stackrel{\_}{0},\stackrel{\_}{1}\right)$ and $\left(\stackrel{\_}{1},\stackrel{\_}{0}\right)$ to $\left(\stackrel{\_}{1},\stackrel{\_}{0}\right)$ for the matrix B₁.

For the introduced method in this section, if the matrix P uses 8 different matrices B       with the two mentioned properties, the obtained lower bound will not change.

The bound can be increased if we use MDS matrices (in GF (2⁸)) instead of the binary matrix B in relation (14). In this case, using the mentioned method, the lower bound of the MNDAS for 8 rounds is increased to 60. For a 4 × 4 MDS matrix the possible double-truncated transitions would be the same as the ones for matrix B. The only difference is that for each active B, 5 is added to the lower bound of MNDAS. The SPN structures using the new diffusion layer, have at       most 6-round impossible differentials. It can be implemented efficiently similar to        Rindael-256 because Π is similar to ShiftRows and B is similar to MixColumns.       The lower bound of the MNDAS for 8 rounds of Rindael-256 is 50 which is much less       than the bound 60 calculated for the proposed SPN. The new SPN can be used to       design a block cipher with a block size of 256 bits.

4 Conclusion

In this paper, we concentrated on the design of binary matrices with suitable cryptographic properties. Firstly, using the AES structure, a new 16 × 16 binary matrix was proposed. Although, this matrix has       appropriate results as far as the active S-boxes for R rounds of the Camellia block cipher is concerned,       its resistance against impossible differential attack is not preferable. To solve this problem,       The Camellia binary matrix idea and byte permutation (similar to ShiftRows in AES ) were utilized       resulting in a new structure. Using this new structure, a 16 × 16 matrix was proposed where 10 rounds       of an SPN structure using this matrix as its diffusion layer has 47 linear and differential active       S-boxes and there is no impossible differential distinguisher for more than 4 rounds.

Due to the limitation of the memory and time for counting the active S-boxes for a 32 × 32 binary matrix,       the counting method mentioned in was modified to provide a lower bound for the active S-boxes.       Then based on 4 × 4 binary matrices, a new structure for 32 × 32 binary matrices was presented.       Using the proposed structure, it was found that the lower bound for the active S-boxes in 8 rounds        of the SPN structure employing this matrix as its diffusion layer is 48. Since the counting method       used for this structure could be extended to non-binary matrices, the 4 × 4 binary matrix was       replaced by a 4 × 4 MDS matrix. The lower bound for the number of active S-boxes is 60 for the       new non-binary structure. The resultant bound is better than the corresponding lower bound for       Rijndael-256 which is 50 [13]. All the proposed diffusion layers proposed in this paper can be efficiently implemented in software.

A Software Implementations

          Now some points are described about the method of implementing of round function on processors with word length 32 or above. In a round function of the SPN structure after the key addition layer which simply is implemented by XOR operations, the Sbox layer and diffusion layer are applied to the input block as follows:        

Q ∘ Π ∘ S

where Q and Π are n × n binary matrices. The above functions are applied to the input block X = (x₁, x₂, ..., x_n), where each x_i, i = 1, 2, ... , n is a byte. Since we can interchange S and Π, Q ∘ Π ∘ S(X) = Q ∘ S ∘ Π(X) . Thus, in the following the method of implementation is described. If all of the 8-bit Sboxes used in S-box layer are the same, to implement Q∘ S for all Qs introduced in this paper it suffices to pre-compute and store the following 4 lookup tables each with 256 4-byte word entries:

          $\begin{array}{cc}{T}_{\mathrm{0111}}\left[x\right]=\left(\begin{array}{cccc}0& s\left[x\right]& s\left[x\right]& s\left[x\right]\end{array}\right),& T_{\mathrm{1011}}\left[x\right]=\left(\begin{array}{cccc}s\left[x\right]& 0& s\left[x\right]& s\left[x\right]\end{array}\right),\\ T_{\mathrm{1101}}\left[x\right]=\left(\begin{array}{cccc}s\left[x\right]& s\left[x\right]& 0& s\left[x\right]\end{array}\right),& T_{\mathrm{1110}}\left[x\right]=\left(\begin{array}{cccc}s\left[x\right]& s\left[x\right]& s\left[x\right]& 0\end{array}\right)\end{array}$        

          On the other hand, to implement the inverse of the round function the following 4 lookup tables are stored:        

          $\begin{array}{cc}{\mathrm{TI}}_{\mathrm{0111}}\left[x\right]=\left(\begin{array}{cccc}0& s^{\mathrm{-1}}\left[x\right]& s^{\mathrm{-1}}\left[x\right]& s^{\mathrm{-1}}\left[x\right]\end{array}\right),& {\mathrm{TI}}_{\mathrm{1011}}\left[x\right]=\left(\begin{array}{cccc}{s}^{\mathrm{-1}}\left[x\right]& 0& s^{\mathrm{-1}}\left[x\right]& s^{\mathrm{-1}}\left[x\right]\end{array}\right),\\ {\mathrm{TI}}_{\mathrm{1101}}\left[x\right]=\left(\begin{array}{cccc}{s}^{\mathrm{-1}}\left[x\right]& s^{\mathrm{-1}}\left[x\right]& 0& s^{\mathrm{-1}}\left[x\right]\end{array}\right),& {\mathrm{TI}}_{\mathrm{1110}}\left[x\right]=\left(\begin{array}{cccc}{s}^{\mathrm{-1}}\left[x\right]& s^{\mathrm{-1}}\left[x\right]& s^{\mathrm{-1}}\left[x\right]& 0\end{array}\right)\end{array}$        

          The matrix Q1 introduced in Section 2 can be divided into 4 independent 4 × 4 sub-blocks. Thus, applying Q1 ∘ S to input vector can be implemented by independent calculation of 4 sub-blocks of the output. Each output sub-block is calculated by 4 table lookups and 3 XOR operations. Calculation of the Q1⁻¹ ∘ S⁻¹ is the same.        

Matrix Q2 introduced in Section 2 can be divided into two 8 × 8 sub-blocks which can be implemented independently. Here, the implementation of the first 8 × 8 sub-block is described. Implementation of the second 8 × 8 sub-block is performed similarly. To compute (y₁, y₂,... ..., y₈), the following vectors are calculated first:        

          $\begin{array}{c}{z}_0=P_{\mathrm{3,0,1,2}}\times \left(\begin{array}{c}s\left[x_1\right]\\ s\left[x_2\right]\\ s\left[x_3\right]\\ s\left[x_4\right]\end{array}\right)\\ =T_{\mathrm{1011}}\left[x_1\right]⨁T_{\mathrm{1101}}\left[x_2\right]⨁T_{\mathrm{1110}}\left[x_3\right]⨁T_{\mathrm{0111}}\left[x_4\right]\end{array}$        

$\begin{array}{c}{z}_1=P_{\mathrm{0,1,2,3}}\times \left(\begin{array}{c}s\left[x_5\right]\\ s\left[x_6\right]\\ s\left[x_7\right]\\ s\left[x_8\right]\end{array}\right)\\ =T_{\mathrm{0111}}\left[x_5\right]⨁T_{\mathrm{1011}}\left[x_6\right]⨁T_{\mathrm{1101}}\left[x_7\right]⨁T_{\mathrm{1110}}\left[x_8\right]\end{array}$

Then (y₁, y₂, y₃, y₄) is computed as follows:

          $\begin{array}{cc}\left(\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_4\end{array}\right)=z_0⨁z_1& \mathrm{(A.1)}\end{array}$        

and (y₅, y₆, y₇, y₈) is computed as follows:

          $\begin{array}{cc}\left(\begin{array}{c}{y}_5\\ y_6\\ y_7\\ y_8\end{array}\right)=\left(\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_4\end{array}\right)⨁z_0⋘8& \mathrm{(A.2)}\end{array}$        

where z₀ ⋘ 8 shows the circular shifting of z₀ by 8 bits. Thus, the calculation of each output sub-block needs 8 table lookups, 8 XOR operations and 1 circular shift operation. To compute (y₉, y₁₀,... ..., y₁₆) the following vectors are calculated first:        

          $\begin{array}{c}{z}_2=P_{\mathrm{1,2,3,0}}\times \left(\begin{array}{c}s\left[x_9\right]\\ s\left[x_{\mathrm{10}}\right]\\ s\left[x_{\mathrm{11}}\right]\\ s\left[x_{\mathrm{12}}\right]\end{array}\right)\\ =T_{\mathrm{1110}}\left[x_9\right]⨁T_{\mathrm{0111}}\left[x_{\mathrm{10}}\right]⨁T_{\mathrm{1011}}\left[x_{\mathrm{11}}\right]⨁T_{\mathrm{1101}}\left[x_{\mathrm{12}}\right]\end{array}$        

  $\begin{array}{c}{z}_3=P_{\mathrm{1,2,3,0}}\times \left(\begin{array}{c}s\left[x_{\mathrm{13}}\right]\\ s\left[x_{\mathrm{14}}\right]\\ s\left[x_{\mathrm{15}}\right]\\ s\left[x_{\mathrm{16}}\right]\end{array}\right)\\ =T_{\mathrm{1110}}\left[x_{\mathrm{13}}\right]⨁T_{\mathrm{0111}}\left[x_{\mathrm{14}}\right]⨁T_{\mathrm{1011}}\left[x_{\mathrm{15}}\right]⨁T_{\mathrm{1101}}\left[x_{\mathrm{16}}\right]\end{array}$

Then (y₉, y₁₀, y₁₁, y₁₂) is computed as follows:

          $\begin{array}{cc}\left(\begin{array}{c}{y}_9\\ y_{\mathrm{10}}\\ y_{\mathrm{11}}\\ y_{\mathrm{12}}\end{array}\right)=z_2⨁z_3& \mathrm{(A.3)}\end{array}$        

and (y₁₃, y₁₄, y₁₅, y₁₆) is computed as follows:        

          $\begin{array}{cc}\left(\begin{array}{c}{y}_{\mathrm{13}}\\ y_{\mathrm{14}}\\ y_{\mathrm{15}}\\ y_{\mathrm{16}}\end{array}\right)=\left(\begin{array}{c}{y}_9\\ y_{\mathrm{10}}\\ y_{\mathrm{11}}\\ y_{\mathrm{12}}\end{array}\right)⋘8⨁z_2& \mathrm{(A.4)}\end{array}$        

          Thus, the calculation of each output sub-block needs 8 table lookups, 8 XOR operations, and 1 circular shift operation.        

Inverse of Q2 is as follows.

          $\begin{array}{cc}{\mathrm{Q2}}^{\mathrm{-1}}=\left(\begin{array}{cccc}{P}_{\mathrm{0,1,2,3}}& P_{\mathrm{0,1,2,3}}& z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}\\ P_{\mathrm{3,0,1,2}}⨁P_{\mathrm{0,1,2,3}}& P_{\mathrm{3,0,1,2}}& z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}\\ z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}& P_{\mathrm{0,1,2,3}}& P_{\mathrm{3,0,1,2}}\\ z_{\mathrm{4\times 4}}& z_{\mathrm{4\times 4}}& P_{\mathrm{0,1,2,3}}⨁P_{\mathrm{3,0,1,2}}& P_{\mathrm{3,0,1,2}}\end{array}\right)& \mathrm{(A.5)}\end{array}$        

It is clear that Q2⁻¹ ∘ S⁻¹ can be implemented similar to Q2 ∘ S.

B Hardware Implementations of Binary Matrix

To hardware implementation of binary matrix

         $\begin{array}{c}{P}_{\mathrm{1,2,3,0}}=\left(\begin{array}{cccc}1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 0\\ 0& 1& 1& 1\end{array}\right)\end{array}$ We can implement this matrix directly or recursive. To implement recursive, these relations as below (x_i’s are inputs and y_i’s are output):

          $\begin{array}{cc}\begin{array}{c}{y}_0=x_0⨁x_2⨁x_3\\ y_1=x_1⨁x_2⨁y_0\\ y_2=x_2⨁x_3⨁y_1\\ y_3=x_3⨁y_0⨁y_1\end{array}& \mathrm{(B.1)}\end{array}$        

If we want to decrease 8 XOR to 7 XOR, we need to define a temporary variable:

          $\begin{array}{cc}\begin{array}{c}\mathrm{temp}=x_0⨁x_1⨁x_2⨁x_3\\ y_0=x_0⨁\mathrm{temp}\\ y_1=x_1⨁\mathrm{temp}\\ y_2=x_2⨁\mathrm{temp}\\ y_3=x_3⨁\mathrm{temp}\end{array}& \mathrm{(B.2)}\end{array}$        

References

1. M. Kanda, S. Moriai, K. Aoki, H. Ueda, Y. Takashima, K. Ohta, and T. Matsumoto. E2- A New 128-Bit Block Cipher. IEICE Transac- tions on Fundamentals of Electronics, Communi- cations and Computer Sciences, E83-A(1):48–59, 2000.
2. K. Aoki, T. Ichikawa, M. Kanda, M. Matsui, S. Moriai, J. Nakajima, and T. Tokita. Camellia: A 128-bit Block Cipher Suitable for Multiple Platforms-Design and Analysis. In SAC 2000, volume 2012, pages 39–56. Springer-Verlag Berlin Heidelberg, 2001.
3. D. Kwon, J. Kim, S. Park, S.H. Sung, Y. Sohn, J.H. Song, Y. Yeom, E-J. Yoon, S. Lee, J. Lee, S. Chee, D. Han, and J. Hong. New Block Cipher ARIA. In ICISC2003, volume 2971, pages 432–445. Springer-Verlag, 2003.
4. Christof Beierle, J´er´emy Jean, Stefan K¨olbl, Gregor Leander, Amir Moradi, Thomas Peyrin, Yu Sasaki, Pascal Sasdrich, and Siang Meng Sim. The skinny family of block ciphers and its low-latency variant mantis. In Advances in Cryptology–CRYPTO 2016: 36th Annual Inter- national Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II 36, pages 123–153. Springer, 2016.
5. Subhadeep Banik, Andrey Bogdanov, Takanori Isobe, Kyoji Shibutani, Harunaga Hiwatari, Toru Akishita, and Francesco Regazzoni. Midori: A block cipher for low energy. In Advances in Cryptology–ASIACRYPT 2015: 21st Interna- tional Conference on the Theory and Application of Cryptology and Information Security, Auck- land, New Zealand, November 29–December 3, 2015, Proceedings, Part II 21, pages 411–436. Springer, 2015..
6. B. Koo, H. Jang, and J. Song. On constructing of a 32 * 32 binary matrix as a diffusion layer for a 256-bit block cipher. In ICISC2006, volume 4296, pages 51–64. Springer-Verlag, 2006.
7. Muharrem Tolga Sakallı, Sedat Akleylek, Bora Aslan, Ercan Bulu¸s, and Fatma Bu¨yu¨ksarac¸og˘lu Sakallı. On the construction of and binary ma- trices with good implementation properties for lightweight block ciphers and hash functions. Mathematical Problems in Engineering, 2014 , 2014.
8. M. Matsui. Linear Cryptanalysis Method for DES Cipher. In EUROCRYPT’93, volume 765, pages 386–397. Springer-Verlag, 1993.
9. E. Biham and A. Shamir. Differential Cryptanalysis of DES-like Cryptosystems. In CRYPTO’90, volume 537, pages 2–21. Springer-Verlag, 1990.
10. J. Daemen.Cipher and Hash Function Design Strategies Based on Linear and Differen- tial Cryptanalysis. PhD thesis, Elektrotechniek Katholieke Universiteit Leuven, Belgium, 1995.
11. Mahdi Sajadieh, Arash Mirzaei, Hamid Mala, and Vincent Rijmen. A new counting method to bound the number of active s-boxes in rijn- dael and 3d. Designs, Codes and Cryptography, 83:327–343, 2017.
12. Hongjun Wu. The hash function jh. Submission to NIST (round 3), 6, 2011.
13. J. Daemen and V. Rijmen. The Design of Rijn- dael: AES - The Advanced Encryption Standard. Springer-Verlag, 2002.