# Optimal MDS matrix - circulant or recursive?

One of the special matrix in $GF(2^q)$ is MDS matrix which can be used in the cryptography like mix column of AES. Two forms of MDS matrices are circulant and recursive.

Which form of MDS matrix (circulant or recursive) is suitable for a cryptographic hardware implentation? Meaning: which of them is optimal?

• To clarify, could you please define "optimal"? There are several ways to interpret that term. Do you mean in the sense of "security", "speed", "ease of implementation", or something else? – e-sushi Jun 8 '17 at 11:17
• @e-sushi I mean security by optimal. In fact the branch number of two cases are $5$ but it is question for me that is it effective the form of matrix in producing active s-box. Thanks for edition and comment. – Amin235 Jun 10 '17 at 14:27

my answer is extension to circulant and recursive.

one property measure to the optimal implementation of MDS matrix in cryptography is the cost of xor (number of xors required to fully implement the MDS matrix ) , depth (number of stages) and the field size (usually 4 or 8 )

according to this paper MDS Matrices with Lightweight Circuits, the native implementation of AES MDS matrix costs 152 xors , with the improved algorithm is reduced to 97 xors and depth of three stages. they searched for others MDS with different structures such as Toeplitz and Hadamard.

Figures below show better MDS matrices in term of implementation compared to circulant AES MDS .

In addition to hardware cost, the security aspect of MDS matrix has appeared in this paper : MixColumns Properties and Attacks on (round-reduced) AES with a Single Secret S-Box, which takes advantage of MDS values.

At the end , it is your call which MDS matrix to be implemented , you need to look it from security and hardware implementation cost.

• Maybe you find this article interesting! – Amin235 Jun 22 '18 at 7:54

Circulant MDS matrices are used in the design of AES (see The design of Rijndael: AES-the advanced encryption standard).

Recursive MDS matrices are easier to compute, thus better for hardware implementations and were actually designed in order to be so (see The PHOTON Family of Lightweight Hash Functions, where they are first introduced and being called "serial" instead of recursive.)

You can see the following block ciphers:

• The New Block Cipher Design (Tigris Cipher) - MECS Press
• The Euphrates Cipher - IJCSI
• New Symmetric Cipher Fast Algorithm of Revertible Operations (FAROQ) Cipher.