Four by four MDS matrices with the fewest XOR gates based on words

Shi Wang; Yongqiang Li; Shizhu Tian; Xiangyong Zeng

doi:10.3934/amc.2021025

Article Contents

2023, Volume 17, Issue 4: 845-872. Doi: 10.3934/amc.2021025

This issue Previous Article On additive MDS codes over small fields Next Article A new twofold Cornacchia-type algorithm and its applications

Four by four MDS matrices with the fewest XOR gates based on words

1.
Faculty of Mathematics and Statistics, Hubei Key Laboratory of Applied Mathematics, Hubei University, Wuhan 430062, China
2.
State Key Laboratory of Information Security, Institute of Information Engineering, , University of Chinese Academy of Sciences, Beijing, China

^* Corresponding author: Xiangyong Zeng
^* Corresponding author: Xiangyong Zeng

Received: April 2021

Revised: May 2021

Early access: July 2021

Published: August 2023

Xiangyong Zeng was supported by Application Foundation Frontier Project of Wuhan Science and Technology Bureau under Grant 2020010601012189 and National Natural Science Foundation of China under Grant 61761166010. Yongqiang Li was supported by National Natural Science Foundation of China under Grant 61772517.

Abstract / Introduction Full Text(HTML) Figure(2) / Table(9) Related Papers Cited by

Abstract

MDS matrices play an important role in the design of block ciphers, and constructing MDS matrices with fewer xor gates is of significant interest for lightweight ciphers. For this topic, Duval and Leurent proposed an approach to construct MDS matrices by using three linear operations in ToSC 2018. Taking words as elements, they found $ 16\times16 $ and $ 32\times 32 $ MDS matrices over $ \mathbb{F}_2 $ with only $ 35 $ xor gates and $ 67 $ xor gates respectively, which are also the best known implementations up to now. Based on the same observation as their work, we consider three linear operations as three kinds of elementary linear operations of matrices, and obtain more MDS matrices with $ 35 $ and $ 67 $ xor gates. In addition, some $ 16\times16 $ or $ 32\times32 $ involutory MDS matrices with only $ 36 $ or $ 72 $ xor gates over $ \mathbb{F}_2 $ are also proposed, which are better than previous results. Moreover, our method can be extended to general linear groups, and we prove that the lower bound of the sequential xor count based on words for $ 4 \times 4 $ MDS matrix over general linear groups is $ 8n+2 $.

Keywords:

Mathematics Subject Classification: Primary: 11T71, 68P25, 94B60.

Citation:

Full Text(HTML)

Figure 1. The implementations circuit of paths in $ 6 $ classes

Download: Full-size image PowerPoint slide

Figure 2. The implementation circuit of MDS matrix $ M $ based on words

Download: Full-size image PowerPoint slide

Table 1. Comparison with MDS matrices with fewest xor gates ($ \alpha_1 $ is the companion matrix of $ X^4 + X + 1 $, and $ \alpha_2 $ is the companion matrix of $ X^8 + X^2 + 1 = \left(X^4 + X + 1\right)^2 $)

Size	Ring	Type	Best	Ref
n=4	$ \mathbb{F}_2[\alpha_1] $	non-involutory	$ 35 $	[10]
	$ \mathbb{F}_2[\alpha_1] $	non-involutory	$ 35 $	Section 4.2
	$ \mathbb{F}_2[\alpha_1] $	involutory	$ 42 $	[20]
	$ \mathbb{F}_2[\alpha_1] $	involutory	$ 36 $	Section 4.3
n=8	$ \mathbb{F}_{2^8} $	AES	$ 92 $	[26]
	$ \mathbb{F}_2[\alpha_2] $	non-involutory	$ 67 $	[10]
	$ \mathbb{F}_2[\alpha_2] $	non-involutory	$ 67 $	Section 4.2
	$ \mathrm{GL}(8, \, \mathbb{F}_2) $	involutory	$ 84 $	[14]
	$ \mathbb{F}_2[\alpha_2] $	involutory	$ 78 $	[16]
	$ \mathbb{F}_2[\alpha_2] $	involutory	$ 72 $	Section 4.3

| Show Table

DownLoad: CSV

Table 2. Circuit implementation of the matrix $ M_0 $ using extra registers

No.	Operation	No.	Operation	No.	Operation
1	$ x_6\leftarrow x_1+x_3 $	2	$ x_7 \leftarrow x_6+x_5 $	3	$ x_8 \leftarrow x_0+x_7[y_0] $
4	$ x_{9} \leftarrow x_2+x_7[y_2] $	5	$ x_{10} \leftarrow x_4+x_7[y_4] $	6	$ x_{11} \leftarrow x_{10}+x_0 $
7	$ x_{12} \leftarrow x_{11}+x_2 $	8	$ x_{13} \leftarrow x_{12}+x_{1}[y_1] $	9	$ x_{14} \leftarrow x_{12}+x_3[y_3] $
10	$ x_{14} \leftarrow x_{12}+x_5[y_5] $

| Show Table

DownLoad: CSV

Table 3. Elementary matrices of Type $\rm{III}$ for $\beta\in\mathbb{F}^*_{2^n}$

$\overline{\mathbf{1}}$	$\overline{\mathbf{2}}$	$\overline{\mathbf{3}}$	$\overline{\mathbf{4}}$	$\overline{\mathbf{5}}$	$\overline{\mathbf{6}}$	$\overline{\mathbf{7}}$	$\overline{\mathbf{8}}$	$\overline{\mathbf{9}}$	$\overline{\mathbf{10}}$	$\overline{\mathbf{11}}$	$\overline{\mathbf{12}}$
$E_{(12)}$	$E_{(13)}$	$ E_{(14)}$	$ E_{(21)} $	$ E_{(23)} $	$ E_{(24)}$	$E_{(31)}$	$ E_{(32)}$	$ E_{(34)}$	$ E_{(41)}$	$E_{(42)}$	$ E_{(43)}$

| Show Table

DownLoad: CSV

Table 4. Dividing the $32$ paths into $6$ classes

$1$	$(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{5}}, \overline{\mathbf{7}}, \overline{\mathbf{11}}, \overline{\mathbf{3}}, \overline{\mathbf{4}}, \overline{\mathbf{12}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{5}}, \overline{\mathbf{7}}, \overline{\mathbf{11}}, \overline{\mathbf{3}}, \overline{\mathbf{12}}, \overline{\mathbf{4}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{5}}, \overline{\mathbf{11}}, \overline{\mathbf{7}}, \overline{\mathbf{3}}, \overline{\mathbf{4}}, \overline{\mathbf{12}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{5}}, \overline{\mathbf{11}}, \overline{\mathbf{7}}, \overline{\mathbf{3}}, \overline{\mathbf{12}}, \overline{\mathbf{4}})$
$2$	$(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{5}}, \overline{\mathbf{10}}, \overline{\mathbf{1}}, \overline{\mathbf{9}}, \overline{\mathbf{5}}, \overline{\mathbf{10}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{5}}, \overline{\mathbf{10}}, \overline{\mathbf{1}}, \overline{\mathbf{9}}, \overline{\mathbf{10}}, \overline{\mathbf{5}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{5}}, \overline{\mathbf{10}}, \overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{5}}, \overline{\mathbf{10}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{5}}, \overline{\mathbf{10}}, \overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{10}}, \overline{\mathbf{5}})$
	$(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{10}}, \overline{\mathbf{5}}, \overline{\mathbf{1}}, \overline{\mathbf{9}}, \overline{\mathbf{5}}, \overline{\mathbf{10}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{10}}, \overline{\mathbf{5}}, \overline{\mathbf{1}}, \overline{\mathbf{9}}, \overline{\mathbf{10}}, \overline{\mathbf{5}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{10}}, \overline{\mathbf{5}}, \overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{5}}, \overline{\mathbf{10}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{10}}, \overline{\mathbf{5}}, \overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{10}}, \overline{\mathbf{5}})$
$3$	$(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{10}}, \overline{\mathbf{2}}, \overline{\mathbf{6}}, \overline{\mathbf{8}}, \overline{\mathbf{4}}, \overline{\mathbf{12}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{10}}, \overline{\mathbf{2}}, \overline{\mathbf{6}}, \overline{\mathbf{8}}, \overline{\mathbf{12}}, \overline{\mathbf{4}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{10}}, \overline{\mathbf{6}}, \overline{\mathbf{2}}, \overline{\mathbf{8}}, \overline{\mathbf{4}}, \overline{\mathbf{12}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{1}}, \overline{\mathbf{10}}, \overline{\mathbf{6}}, \overline{\mathbf{2}}, \overline{\mathbf{8}}, \overline{\mathbf{12}}, \overline{\mathbf{4}})$
$4$	$(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{2}}, \overline{\mathbf{8}}, \overline{\mathbf{10}}, \overline{\mathbf{6}}, \overline{\mathbf{1}}, \overline{\mathbf{12}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{2}}, \overline{\mathbf{8}}, \overline{\mathbf{10}}, \overline{\mathbf{6}}, \overline{\mathbf{12}}, \overline{\mathbf{1}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{2}}, \overline{\mathbf{10}}, \overline{\mathbf{8}}, \overline{\mathbf{6}}, \overline{\mathbf{1}}, \overline{\mathbf{12}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{2}}, \overline{\mathbf{10}}, \overline{\mathbf{8}}, \overline{\mathbf{6}}, \overline{\mathbf{12}}, \overline{\mathbf{1}})$
$5$	$(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{2}}, \overline{\mathbf{11}}, \overline{\mathbf{4}}, \overline{\mathbf{9}}, \overline{\mathbf{2}}, \overline{\mathbf{11}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{2}}, \overline{\mathbf{11}}, \overline{\mathbf{4}}, \overline{\mathbf{9}}, \overline{\mathbf{11}}, \overline{\mathbf{2}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{2}}, \overline{\mathbf{11}}, \overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{2}}, \overline{\mathbf{11}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{2}}, \overline{\mathbf{11}}, \overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{11}}, \overline{\mathbf{2}})$
	$(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{11}}, \overline{\mathbf{2}}, \overline{\mathbf{4}}, \overline{\mathbf{9}}, \overline{\mathbf{2}}, \overline{\mathbf{11}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{11}}, \overline{\mathbf{2}}, \overline{\mathbf{4}}, \overline{\mathbf{9}}, \overline{\mathbf{11}}, \overline{\mathbf{2}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{11}}, \overline{\mathbf{2}}, \overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{2}}, \overline{\mathbf{11}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{11}}, \overline{\mathbf{2}}, \overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{11}}, \overline{\mathbf{2}})$
$6$	$(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{11}}, \overline{\mathbf{3}}, \overline{\mathbf{5}}, \overline{\mathbf{7}}, \overline{\mathbf{1}}, \overline{\mathbf{12}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{11}}, \overline{\mathbf{3}}, \overline{\mathbf{5}}, \overline{\mathbf{7}}, \overline{\mathbf{12}}, \overline{\mathbf{1}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{11}}, \overline{\mathbf{5}}, \overline{\mathbf{3}}, \overline{\mathbf{7}}, \overline{\mathbf{1}}, \overline{\mathbf{12}})$ $(\overline{\mathbf{9}}, \overline{\mathbf{4}}, \overline{\mathbf{11}}, \overline{\mathbf{5}}, \overline{\mathbf{3}}, \overline{\mathbf{7}}, \overline{\mathbf{12}}, \overline{\mathbf{1}})$

| Show Table

DownLoad: CSV

Table 5. The minimal polynomial is $x^4+x+1 = 0$ and $A = \mathrm{companion}(1, 1, 0, 0)$

No.	$M_{11}$	$M_{12}$	$M_{13}$	$M_{14}$	$M_{21}$	$M_{22}$	$M_{23}$	$M_{24}$
$1$	$I$	$I + A^2$	$A^2$	$A + A^2$	$I$	$A + I + A^2$	$A + A^2$	$A^2$
$2$	$A$	$A + I + A^3$	$I + A^3$	$A^3$	$A$	$A + A^3$	$A^3$	$I + A^3$
$3$	$I$	$I + A^2$	$A^2$	$A + A^2$	$I$	$A + I + A^2$	$A + A^2$	$A^2$
$4$	$I$	$A^2 + A^3$	$I + A^2 + A^3$	$A^2$	$I$	$I + A^2$	$A^2$	$I + A^2 + A^3$
$5$	$I + A^3$	$A + I + A^3$	$A$	$A + I$	$I + A^3$	$A + A^3$	$A + I$	$A$
$6$	$I$	$A^2 + A^3$	$I + A^2 + A^3$	$A^2$	$I$	$I + A^2$	$A^2$	$I + A^2 + A^3$
$7$	$I$	$A + I$	$A$	$A$	$A^2$	$A + A^2$	$A + I$	$I$
$8$	$I$	$A + I$	$A$	$A$	$A$	$A + I$	$A^3$	$I + A^3$
$9$	$I$	$A^3$	$I + A^3$	$I + A^3$	$I + A^3$	$A^3$	$A + I$	$A$
$10$	$I$	$A^3$	$I + A^3$	$I + A^3$	$I + A^2 + A^3$	$A^2$	$A^3$	$I$
No.	$M_{31}$	$M_{32}$	$M_{33}$	$M_{34}$	$M_{41}$	$M_{42}$	$M_{43}$	$M_{44}$
$1$	$A$	$A$	$I$	$I$	$A$	$A + A^2$	$I + A^2$	$A + I + A^2$
$2$	$I$	$I$	$A$	$A$	$I$	$A^3$	$A + I + A^3$	$A + A^3$
$3$	$I$	$I$	$I + A^3$	$I + A^3$	$I$	$A + I$	$A + I + A^3$	$A + A^3$
$4$	$I$	$I$	$A$	$A$	$I$	$A^3$	$A + I + A^3$	$A + A^3$
$5$	$I$	$I$	$I + A^3$	$I + A^3$	$I$	$A + I$	$A + I + A^3$	$A + A^3$
$6$	$I + A^3$	$I + A^3$	$I$	$I$	$I + A^3$	$A^2$	$A^2 + A^3$	$I + A^2$
$7$	$A^2$	$A^2$	$I$	$A + I$	$A + I$	$I$	$A$	$A + I$
$8$	$A$	$A$	$I + A^3$	$A^3$	$A + I$	$I$	$A$	$A + I$
$9$	$I + A^3$	$I + A^3$	$A$	$A + I$	$A^3$	$I$	$I + A^3$	$A^3$
$10$	$I + A^2 + A^3$	$I + A^2 + A^3$	$I$	$A^3$	$A^3$	$I$	$I + A^3$	$A^3$

| Show Table

DownLoad: CSV

Table 6. The decompositions of $10$ classes of MDS matrices with $8n+3$ sw-xor

$M_1$	$\overline{\mathbf{12}}(\mathbf{1})\overline{\mathbf{4}}(\mathbf{1})\overline{\mathbf{3}}(\mathbf{1})E_{(4)}(A)\overline{\mathbf{11}}(\mathbf{1}) \overline{\mathbf{7}}(A)E_{(2)}(A)\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{1}}(\mathbf{1})\overline{\mathbf{9}}(\mathbf{1})$
$M_2$	$\overline{\mathbf{12}}(\mathbf{1})\overline{\mathbf{4}}(\mathbf{1})\overline{\mathbf{3}}(\mathbf{1})\overline{\mathbf{11}}(A^{-1})E_{(1)}(A) \overline{\mathbf{7}}(\mathbf{1})E_{(3)}(A)\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{1}}(\mathbf{1})\overline{\mathbf{9}}(\mathbf{1})$
$M_3$	$\overline{\mathbf{12}}(\mathbf{1})\overline{\mathbf{4}}(\mathbf{1})\overline{\mathbf{3}}(A)\overline{\mathbf{11}}(\mathbf{1}) \overline{\mathbf{7}}(\mathbf{1})E_{(2)}(A)E_{(3)}(A^{-1})\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{1}}(\mathbf{1})\overline{\mathbf{9}}(\mathbf{1})$
$M_4$	$\overline{\mathbf{12}}(\mathbf{1})\overline{\mathbf{4}}(\mathbf{1})\overline{\mathbf{3}}(A^{-1})\overline{\mathbf{11}}(\mathbf{1})E_{(2)}(A^{-\mathbf{1}}) \overline{\mathbf{7}}(\mathbf{1})E_{(3)}(A)\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{\mathbf{1}}}(\mathbf{1})\overline{\mathbf{9}}(\mathbf{1})$
$M_5$	$\overline{\mathbf{12}}(\mathbf{1})\overline{\mathbf{4}}(\mathbf{1})\overline{\mathbf{3}}(\mathbf{1})\overline{\mathbf{11}}(A)E_{(1)}(A^{-1}) \overline{\mathbf{7}}(\mathbf{1})E_{(3)}(A^{-1})\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{1}}(\mathbf{1})\overline{\mathbf{9}}(\mathbf{1})$
$M_6$	$\overline{\mathbf{12}}(\mathbf{1})\overline{\mathbf{4}}(\mathbf{1})\overline{\mathbf{3}}(\mathbf{1})E_{(4)}(A^{-1})\overline{\mathbf{11}}(\mathbf{1}) \overline{\mathbf{7}}(A^{-1})E_{(2)}(A^{-1})\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{1}}(\mathbf{1})\overline{\mathbf{9}}(\mathbf{1})$
$ M_7$	$\overline{\mathbf{10}}(\mathbf{1})\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{9}}(A)\overline{\mathbf{\mathbf{1}}}(\mathbf{1}) \overline{\mathbf{10}}(A)E_{(2)}(A)\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{\mathbf{1}}}(\mathbf{1})\overline{\mathbf{9}}(\mathbf{1}) $
$ M_8$	$\overline{\mathbf{\mathbf{1}0}}(\mathbf{1})\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{9}}(\mathbf{1})\overline{\mathbf{\mathbf{1}}}(A) \overline{\mathbf{\mathbf{1}0}}(A)E_{(3)}(A^{-1})\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{\mathbf{1}}}(\mathbf{1})\overline{\mathbf{9}}(\mathbf{1}) $
$ M_9$	$\overline{\mathbf{10}}(\mathbf{1})\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{9}}(\mathbf{1})\overline{\mathbf{\mathbf{1}}}(A^{-1}) \overline{\mathbf{10}}(A^{-1})E_{(3)}(A)\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{\mathbf{1}}}(\mathbf{1})\overline{\mathbf{9}}(\mathbf{1}) $
$ M_{10}$	$\overline{\mathbf{10}}(\mathbf{1})\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{9}}(A^{-1})\overline{\mathbf{1}}(\mathbf{1}) \overline{\mathbf{10}}(A^{-1})E_{(3)}(A^{-1})\overline{\mathbf{5}}(\mathbf{1})\overline{\mathbf{1}}(\mathbf{1})\overline{\mathbf{9}}(\mathbf{1}) $

| Show Table

DownLoad: CSV

Table 7. The minimal polynomial is $x^8+x^2+1 = 0$ and $A = \mathrm{companion}(1, 0, 1, 0, 0, 0, 0, 0)$

No.	$M_{11}$	$M_{12}$	$M_{13}$	$M_{14}$	$M_{21}$	$M_{22}$	$M_{23}$	$M_{24}$
$1$	$I$	$I + A^2$	$A^2$	$A + A^2$	$I$	$A + I + A^2$	$A + A^2$	$A^2$
$2$	$A$	$A^7$	$A + A^7$	$A + I + A^7$	$A$	$I + A^7$	$A + I + A^7$	$A + A^7$
$3$	$I$	$I + A^2$	$A^2$	$A + A^2$	$I$	$A + I + A^2$	$A + A^2$	$A^2$
$4$	$I$	$A^6$	$I + A^6$	$A + I + A^6 + A^7$	$I$	$A + A^6 + A^7$	$A + I + A^6 + A^7$	$I + A^6$
$5$	$A + A^7$	$A^7$	$A$	$A + I$	$A + A^7$	$I + A^7$	$A + I$	$A$
$6$	$I$	$A^6$	$I + A^6$	$A + I + A^6 + A^7$	$I$	$A + A^6 + A^7$	$A + I + A^6 + A^7$	$I + A^6$
$7$\thanks	$I$	$A + I$	$A$	$A$	$A^2$	$A + A^2$	$A + I$	$I$
$8$	$I$	$A + I$	$A$	$A$	$A$	$A + I$	$A + I + A^7$	$A + A^7$
$9$	$I$	$A + I + A^7$	$A + A^7$	$A + A^7$	$A + A^7$	$A + I + A^7$	$A + I$	$A$
$10$	$I$	$A + I + A^7$	$A + A^7$	$A + A^7$	$I + A^6$	$A + I + A^6 + A^7$	$A + I + A^7$	$I$
No.	$M_{31}$	$M_{32}$	$M_{33}$	$M_{34}$	$M_{41}$	$M_{42}$	$M_{43}$	$M_{44}$
$1$	$A$	$A$	$I$	$I$	$A$	$A + A^2$	$I + A^2$	$A + I + A^2$
$2$	$I$	$I$	$A$	$A$	$I$	$A + I + A^7$	$A^7$	$I + A^7$
$3$	$I$	$I$	$A + A^7$	$A + A^7$	$I$	$A + I$	$A^7$	$I + A^7$
$4$	$I$	$I$	$A$	$A$	$I$	$A + I + A^7$	$A^7$	$I + A^7$
$5$	$I$	$I$	$A + A^7$	$A + A^7$	$I$	$A + I$	$A^7$	$I + A^7$
$6$	$A + A^7$	$A + A^7$	$I$	$I$	$A + A^7$	$A + I + A^6 + A^7$	$A^6$	$A + A^6 + A^7$
$7$	$A^2$	$A^2$	$I$	$A + I$	$A + I$	$I$	$A$	$A + I$
$8$	$A$	$A$	$A + A^7$	$A + I + A^7$	$A + I$	$I$	$A$	$A + I$
$9$	$A + A^7$	$A + A^7$	$A$	$A + I$	$A + I + A^7$	$I$	$A + A^7$	$A + I + A^7$
$10$	$I + A^6$	$I + A^6$	$I$	$A + I + A^7$	$A + I + A^7$	$I$	$A + A^7$	$A + I + A^7$

| Show Table

DownLoad: CSV

Table 8. The minimal polynomial is $ x^4+x+1 = 0 $ and $ A = \mathrm{companion}(1, 1, 0, 0) $

No.	$ M_{11} $	$ M_{12} $	$ M_{13} $	$ M_{14} $	$ M_{21} $	$ M_{22} $	$ M_{23} $	$ M_{24} $
$ 1 $	$ I + A^2 + A^3 $	$ A + I + A^3 $	$ A + I $	$ A + A^3 $	$ I + A^2 + A^3 $	$ A + I + A^2 + A^3 $	$ I $	$ A^3 $
$ 2 $	$ I + A^3 $	$ A + I + A^2 + A^3 $	$ A^2 + A^3 $	$ A + A^2 + A^3 $	$ I + A^3 $	$ I + A^2 + A^3 $	$ A^3 $	$ A + A^3 $
$ 3 $	$ I + A^3 $	$ A + I + A^2 + A^3 $	$ A + A^2 $	$ A + I + A^2 $	$ I + A^3 $	$ I + A^2 + A^3 $	$ A^2 $	$ I + A^2 $
$ 4 $	$ I $	$ A $	$ A + I $	$ A + I + A^2 $	$ I $	$ A + I $	$ A $	$ A + A^2 $
$ 5 $	$ I + A^3 $	$ A + I + A^2 + A^3 $	$ A + A^2 $	$ A^2 $	$ I + A^3 $	$ I + A^2 + A^3 $	$ A^2 $	$ A + A^2 $
$ 6 $	$ I + A^2 + A^3 $	$ A^2 + A^3 $	$ A + I $	$ A + A^3 $	$ I + A^3 $	$ A + I + A^2 + A^3 $	$ A $	$ A + I $
$ 7 $	$ I $	$ A^2 $	$ I + A^2 $	$ A + I + A^2 $	$ I $	$ I + A^2 $	$ A^2 $	$ A + A^2 $
$ 8 $	$ I + A^2 + A^3 $	$ A + I + A^3 $	$ A + A^2 $	$ A + I + A^2 $	$ I + A^2 + A^3 $	$ A + I + A^2 + A^3 $	$ A $	$ A + I $
$ 9 $	$ I $	$ A $	$ A + I $	$ A + A^3 $	$ I $	$ A + I $	$ A $	$ A + I $
$ 10 $	$ I $	$ A $	$ A^3 $	$ A + A^3 $	$ I $	$ A + I $	$ I $	$ A + I $
No.	$ M_{11} $	$ M_{12} $	$ M_{13} $	$ M_{14} $	$ M_{21} $	$ M_{22} $	$ M_{23} $	$ M_{24} $
$ 1 $	$ I $	$ I + A^2 $	$ A + I $	$ A $	$ I $	$ I $	$ I $	$ I $
$ 2 $	$ I $	$ A + I $	$ I + A^2 $	$ A^2 $	$ I $	$ I $	$ I $	$ I $
$ 3 $	$ A $	$ A + A^2 $	$ I + A^2 $	$ A^2 $	$ A $	$ A $	$ I $	$ I $
$ 4 $	$ I + A^3 $	$ A + I + A^3 $	$ A + I + A^2 + A^3 $	$ A + I + A^3 $	$ I + A^3 $	$ I + A^3 $	$ I + A^2 + A^3 $	$ I + A^2 + A^3 $
$ 5 $	$ I $	$ I + A^2 $	$ I + A^2 + A^3 $	$ A + I + A^2 + A^3 $	$ I $	$ I $	$ I + A^3 $	$ I + A^3 $
$ 6 $	$ I $	$ A + I + A^3 $	$ A + I $	$ A $	$ I $	$ I + A^3 $	$ I $	$ I $
$ 7 $	$ A $	$ A + A^2 $	$ I + A^2 + A^3 $	$ A + I + A^2 + A^3 $	$ A $	$ A $	$ I + A^3 $	$ I + A^3 $
$ 8 $	$ I + A^3 $	$ A + I + A^3 $	$ A + I $	$ A $	$ I + A^3 $	$ I + A^3 $	$ I $	$ I $
$ 9 $	$ I + A^3 $	$ A + I + A^3 $	$ A + I + A^2 + A^3 $	$ A^2 + A^3 $	$ I $	$ I $	$ I + A^3 $	$ I + A^2 + A^3 $
$ 10 $	$ I $	$ I + A^2 $	$ A + I + A^2 + A^3 $	$ A + I + A^3 $	$ I $	$ I $	$ I + A^2 + A^3 $	$ I + A^2 + A^3 $

| Show Table

DownLoad: CSV

Table 9. The minimal polynomial is $ x^8+x^2+1 = 0 $ and $ A = \mathrm{companion}(1, 0, 1, 0, 0, 0, 0, 0) $

No.	$ M_{11} $	$ M_{12} $	$ M_{13} $	$ M_{14} $	$ M_{21} $	$ M_{22} $	$ M_{23} $	$ M_{24} $
$ 1 $	$ I + A^4 + A^6 $	$ A^2+ I + A^6 $	$ A^2+ I $	$ A^2+ A^6 $	$ I + A^4 + A^6 $	$ A^2+ I + A^4 + A^6 $	$ I $	$ A^6 $
$ 2 $	$ I + A^6 $	$ A^2+ I + A^4 + A^6 $	$ A^4 + A^6 $	$ A^2+ A^4 + A^6 $	$ I + A^6 $	$ I + A^4 + A^6 $	$ A^6 $	$ A^2+ A^6 $
$ 3 $	$ I + A^6 $	$ A^2+ I + A^4 + A^6 $	$ A^2+ A^4 $	$ A^2+ I + A^4 $	$ I + A^6 $	$ I + A^4 + A^6 $	$ A^4 $	$ I + A^4 $
$ 4 $	$ I $	$ A^2 $	$ A^2+ I $	$ A^2+ I + A^4 $	$ I $	$ A^2+ I $	$ A^2 $	$ A^2+ A^4 $
$ 5 $	$ I + A^6 $	$ A^2+ I + A^4 + A^6 $	$ A^2+ A^4 $	$ A^4 $	$ I + A^6 $	$ I + A^4 + A^6 $	$ A^4 $	$ A^2+ A^4 $
$ 6 $	$ I + A^4 + A^6 $	$ A^4 + A^6 $	$ A^2+ I $	$ A^2+ A^6 $	$ I + A^6 $	$ A^2+ I + A^4 + A^6 $	$ A^2 $	$ A^2+ I $
$ 7 $	$ I $	$ A^4 $	$ I + A^4 $	$ A^2+ I + A^4 $	$ I $	$ I + A^4 $	$ A^4 $	$ A^2+ A^4 $
$ 8 $	$ I + A^4 + A^6 $	$ A^2+ I + A^6 $	$ A^2+ A^4 $	$ A^2+ I + A^4 $	$ I + A^4 + A^6 $	$ A^2+ I + A^4 + A^6 $	$ A^2 $	$ A^2+ I $
$ 9 $	$ I $	$ A^2 $	$ A^2+ I $	$ A^2+ A^6 $	$ I $	$ A^2+ I $	$ A^2 $	$ A^2+ I $
$ 10 $	$ I $	$ A^2 $	$ A^6 $	$ A^2+ A^6 $	$ I $	$ A^2+ I $	$ I $	$ A^2+ I $
No.	$ M_{11} $	$ M_{12} $	$ M_{13} $	$ M_{14} $	$ M_{21} $	$ M_{22} $	$ M_{23} $	$ M_{24} $
$ 1 $	$ I $	$ I + A^4 $	$ A^2+ I $	$ A^2 $	$ I $	$ I $	$ I $	$ I $
$ 2 $	$ I $	$ A^2+ I $	$ I + A^4 $	$ A^4 $	$ I $	$ I $	$ I $	$ I $
$ 3 $	$ A^2 $	$ A^2+ A^4 $	$ I + A^4 $	$ A^4 $	$ A^2 $	$ A^2 $	$ I $	$ I $
$ 4 $	$ I + A^6 $	$ A^2+ I + A^6 $	$ A^2+ I + A^4 + A^6 $	$ A^2+ I + A^6 $	$ I + A^6 $	$ I + A^6 $	$ I + A^4 + A^6 $	$ I + A^4 + A^6 $
$ 5 $	$ I $	$ I + A^4 $	$ I + A^4 + A^6 $	$ A^2+ I + A^4 + A^6 $	$ I $	$ I $	$ I + A^6 $	$ I + A^6 $
$ 6 $	$ I $	$ A^2+ I + A^6 $	$ A^2+ I $	$ A^2 $	$ I $	$ I + A^6 $	$ I $	$ I $
$ 7 $	$ A^2 $	$ A^2+ A^4 $	$ I + A^4 + A^6 $	$ A^2+ I + A^4 + A^6 $	$ A^2 $	$ A^2 $	$ I + A^6 $	$ I + A^6 $
$ 8 $	$ I + A^6 $	$ A^2+ I + A^6 $	$ A^2+ I $	$ A^2 $	$ I + A^6 $	$ I + A^6 $	$ I $	$ I $
$ 9 $	$ I + A^6 $	$ A^2+ I + A^6 $	$ A^2+ I + A^4 + A^6 $	$ A^4 + A^6 $	$ I $	$ I $	$ I + A^6 $	$ I + A^4 + A^6 $
$ 10 $	$ I $	$ I + A^4 $	$ A^2+ I + A^4 + A^6 $	$ A^2+ I + A^6 $	$ I $	$ I $	$ I + A^4 + A^6 $	$ I + A^4 + A^6 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	R. Avanzi, The QARMA block cipher family. Almost MDS matrices over rings with zero divisors, nearly symmetric even-mansour constructions with non-involutory central rounds, and search heuristics for low-latency s-boxes, IACR Trans. Symmetric Cryptol., 2017 (2017), 4-44. doi: 10.46586/tosc.v2017.i1.4-44.
[2]	S. Banik, A. Bogdanov, T. Isobe, K. Shibutani, H. Hiwatari, T. Akishita and F. Regazzoni, Midori: A block cipher for low energy (extended version), ASIACRYPT 2015, Lecture Notes in Computer Science, 9453 (2015), 411-436. doi: 10.1007/978-3-662-48800-3_17.
[3]	S. Banik, Y. Funabiki and T. Isobe, More results on shortest linear programs, Advances in Information and Computer Security - 14th International Workshop on Security, IWSEC 2019, Lecture Notes in Computer Science, 11689 (2019), 109–128. doi: 10.1007/978-3-030-26834-3_7.
[4]	S. Banik, S. K. Pandey, T. Peyrin, Y. Sasaki, S. M. Sim and Y. Todo, GIFT: A small present - towards reaching the limit of lightweight encryption, In: Cryptographic Hardware and Embedded Systems 2017, Lecture Notes in Computer Science, 10529 (2017), 321–345. doi: 10.1007/978-3-319-66787-4\_16.
[5]	C. Beierle, T. Kranz and G. Leander, Lightweight multiplication in ${\rm{GF}}(2^n)$ with applications to MDS matrices, CRYPTO 2016, Lecture Notes in Computer Science, 9814 (2016), 625-653. doi: 10.1007/978-3-662-53018-4_23.
[6]	A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin and C. Vikkelsoe, PRESENT: An ultra-lightweight block cipher, Cryptographic Hardware and Embedded Systems 2007, 4227 (2007), 450-466. doi: 10.1007/978-3-540-74735-2_31.
[7]	J. Borghoff, A. Canteaut, T. Güneysu, E. B. Kavun, M. Knezevic, L. R. Knudsen, G. Leander, V. Nikov, C. Paar, C. Rechberger, P. Rombouts, S. S. Thomsen and T. Yalç, PRINCE - A low-latency block cipher for pervasive computing applications - extended abstract, ASIACRYPT 2012, Lecture Notes in Computer Science, 7658 (2012), 208-225. doi: 10.1007/978-3-642-34961-4\_14.
[8]	J. Boyar, P. Matthews and R. Peralta, Logic minimization techniques with applications to cryptology, J. Cryptology, 26 (2013), 280-312. doi: 10.1007/s00145-012-9124-7.
[9]	J. Daemen and V. Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard, Information Security and Cryptography. Springer, 2002. doi: 10.1007/978-3-662-04722-4.
[10]	S. Duval and G. Leurent, MDS matrices with lightweight circuits, IACR Trans. Symmetric Cryptol., 2018 (2018), 48-78. doi: 10.13154/tosc.v2018.i2.48-78.
[11]	J. Guo, T. Peyrin and A. Poschmann, The PHOTON family of lightweight hash functions, CRYPTO 2011, Lecture Notes in Computer Science, 6841 (2011), 222-239. doi: 10.1007/978-3-642-22792-9_13.
[12]	J. Guo, T. Peyrin, A. Poschmann and M. J. B. Robshaw, The LED block cipher, Cryptographic Hardware and Embedded Systems 2011, Lecture Notes in Computer Science, 6917 (2011), 326-341. doi: 10.1007/978-3-642-23951-9_22.
[13]	J. Jean, T. Peyrin, S. M. Sim and J. Tourteaux, Optimizing implementations of lightweight building blocks, IACR Trans. Symmetric Cryptol., 2017 (2017), 130-168. doi: 10.13154/tosc.v2017.i4.130-168.
[14]	T. Kranz, G. Leander, K. Stoffelen and F. Wiemer, Shorter linear straight-line programs for MDS matrices, IACR Trans. Symmetric Cryptol., 2017 (2017), 188-211. doi: 10.46586/tosc.v2017.i4.188-211.
[15]	C. Li and Q. Wang, Design of lightweight linear diffusion layers from near-mds matrices, IACR Trans. Symmetric Cryptol., 2017 (2017), 129-155. doi: 10.13154/tosc.v2017.i1.129-155.
[16]	S. Li, S. Sun, C. Li, Z. Wei and L. Hu, Constructing low-latency involutory MDS matrices with lightweight circuits, IACR Trans. Symmetric Cryptol., 2019 (2019), 84-117. doi: 10.46586/tosc.v2019.i1.84-117.
[17]	Y. Li and M. Wang, On the construction of lightweight circulant involutory MDS matrices, Fast Software Encryption 2016, Lecture Notes in Computer Science, 9783 (2016), 121-139. doi: 10.1007/978-3-662-52993-5_7.
[18]	M. Liu and S. M. Sim, Lightweight MDS generalized circulant matrices, Fast Software Encryption 2016, Lecture Notes in Computer Science, 9783 (2016), 101-120. doi: 10.1007/978-3-662-52993-5_6.
[19]	F. J. Macwilliams and N. J. A. Sloane, The theory of error correcting codes, North-Holland Mathematical Library, Amsterdam-New York Oxford: North-Holland Publishing Company, 16 (1977), 370-762.
[20]	S. Sarkar and H. Syed, Lightweight diffusion layer: Importance of toeplitz matrices, ACR Trans. Symmetric Cryptol., 2016 (2016), 95-113. doi: 10.13154/tosc.v2016.i1.95-113.
[21]	S. M. Sim, K. Khoo, F. E. Oggier and T. Peyrin, Lightweight MDS involution matrices, Fast Software Encryption 2015, 9054 (2015), 471-493. doi: 10.1007/978-3-662-48116-5_23.
[22]	F. X. Standaert, G. Piret, G. Rouvroy, J. J. Quisquater and J. D. Legat, ICEBERG: An involutional cipher effcient for block encryption in reconfigurable hardware, Fast Software Encryption 2004, 3017 (2004), 279-299.
[23]	Q. Q Tan and T. Peyrin, Improved heuristics for short linear programs, IACR Trans. Cryptogr., 2020 (2020), 203-230. doi: 10.13154/tches.v2020.i1.203-230.
[24]	A. Visconti, C. V. Schiavo and R. Peralta, Improved upper bounds for the expected circuit complexity of dense systems of linear equations over ${\rm{GF}}(2)$, Information Processing Letters, 137 (2018), 1-5. doi: 10.1016/j.ipl.2018.04.010.
[25]	S. Wu, M. Wang and W. Wu, Recursive diffusion layers for (lightweight) block ciphers and hash functions, Selected Areas in Cryptography 2012, Lecture Notes in Computer Science, 7707 (2012), 355-371. doi: 10.1007/978-3-642-35999-6_23.
[26]	Z. Xiang, X. Zeng, D. Lin, Z. Bao and S. Zhang, Optimizing implementations of linear layers, IACR Trans. Symmetric Cryptol., 2020 (2020), 120-145. doi: 10.46586/tosc.v2020.i2.120-145.
[27]	W. Zhang, Z. Bao, D. Lin, V. Rijmen, B. Yang and I. Verbauwhede, RECTANGLE: A bit-slice lightweight block cipher suitable for multiple platforms, Science China Information Sciences, 58 (2015), 1-15. doi: 10.1007/s11432-015-5459-7.
[28]	L. Zhou, L. Wang and Y. Sun, On efficient constructions of lightweight MDS matrices, IACR Trans. Symmetric Cryptol., 2018 (2018), 180-200. doi: 10.46586/tosc.v2018.i1.180-200.