We know that MDS matrices are used in the diffusion layers of block ciphers.

My question: what types of MDS matrices can be applied to serial or round-based implementations or both of them?

I appreciate you to address some references.


what types of MDS matrices can be applied to serial or round-based implementations or both of them?

Serial matrices utilise a trade-off to reduce hardware requirement while incurring additional time cost. Examples of MDS matrices that can be serialized implemented are : cyclic , Hadmard, linear feedback serial (LFS), sparse diagonal serial invertible (DSI), ref. LED, PHOTON, PRIMATES use efficient serialized MDS matrices, ref.

It is possible to transform serial MDS to round-based , as following stated in ref.

One may also consider unrolling DSI/LFS matrices to simulate round- based matrices for comparison with cyclic/Hadamard matrices in a round-based implementation scenario. That is to implement k copies of DSI/LFS matrices in series to achieve the MDS property in one clock cycle. The XOR count of all the matrices would simply be k times of what the tables have shown

MDS matrix is defined over $F_{2^n}$ and the choice of basis is important on implementation efficiency. for round-based hardware implementation, the choice of basis is important in lightweight construction. ref

I sugest to read the following papers to obtain deep knowledge:

  1. Lightweight MDS Serial-type Matrices with Minimal Fixed XOR Count
  2. Shorter Linear Straight-Line Programs for MDS Matrices Yet another XOR Count Paper
  3. Lightweight Multiplication in GF(2n) with Applications to MDS Matrices
  • $\begingroup$ First of all, I want to appreciate for your complete answer. I have two questions. My first question: consider the sparse matrices that are constructed from Generalized type-II Feistel schemes which are given in FSE19. Is the mentioned matrices can be implemented in serial implementation. In other words, you said that "It is possible to transform serial MDS to round-based", now what about its inverse which means is it possible to transform round-based MDS to serial? $\endgroup$ – user0410 Mar 27 at 17:53
  • $\begingroup$ My second question: recently lightweight block ciphers such as SIMON/SPECK, Robin (FSE14), Midori (Asiacrypt15), SIMECK (CHES15), SKINNY (CRYPTO16), SPARX (Asiacrypt16), GIFT (CHES17) and CRAFT (FSE19) did not used MDS matrices in their diffusion layer. Now, is it possible to ask you what is the application of lightweight MDS matrices? In fact, when the lightweight block ciphers do not apply the MDS matrices in their designing , so what is the impact or usage of lightweight MDS matrices? Thanks in advance. $\endgroup$ – user0410 Mar 27 at 18:07
  • $\begingroup$ Excuse me can I ask you to tell your idea about my questions especially my second question. Thanks. $\endgroup$ – user0410 Mar 28 at 14:23
  • 1
    $\begingroup$ SIMON/SPECK , SIMECK are arx based (addition rotation xor). GIFT, SKINNY and MIDORI use almost MDS which has a branch number of 4 while branch number of MDS is 5, MDS provide faster diffusion than almost MDS in less rounds. but almost MDS costs less area to implement especially hardware , so the research of lightweight MDS aims to construct lightweight and secure cipher and (higher performance) less rounds of diffusion. I hope you received it. $\endgroup$ – hardyrama Mar 28 at 14:33
  • $\begingroup$ Thanks for the useful comment. You said SKINNY used almost MDS. Based on this reference, in page 10, it is mentioned that the mix-column of SKINNY is $$ {\bf M}=\left( \begin {array}{cccc} 1&0&1&1\\ 1&0&0&0 \\ 0&1&1&0\\ 1&0&1&0\end {array} \right). $$ It is clear that the branch number of $\bf M$ is not 4. My question is: where is my mistake? Thanks $\endgroup$ – user0410 Mar 28 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.