A new hybrid method combining search and direct based construction ideas to generate all 4 × 4 involutory maximum distance separable (MDS) matrices over binary field extensions

Tuncay G., Sakallı F. B., KURT PEHLİVANOĞLU M., Yılmazgüç G. G., Akleylek S., SAKALLI M. T.

PeerJ Computer Science, vol.9, 2023 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 9
  • Publication Date: 2023
  • Doi Number: 10.7717/peerj-cs.1577
  • Journal Name: PeerJ Computer Science
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Compendex, Directory of Open Access Journals
  • Keywords: A new hybrid method, Diffusion layer, Involutory matrices, Lightweight Cryptography, MDS matrices
  • Ondokuz Mayıs University Affiliated: Yes


This article presents a new hybrid method (combining search based methods and direct construction methods) to generate all 4 * 4 involutory maximum distance separable (MDS) matrices over F2m. The proposed method reduces the search space complexity at the level of pffinffiffi, where n represents the number of all 4 * 4 invertible matrices over F2m to be searched for. Hence, this enables us to generate all 4 * 4 involutory MDS matrices over F23 and F24. After applying global optimization technique that supports higher Exclusive-OR (XOR) gates (e.g., XOR3, XOR4) to the generated matrices, to the best of our knowledge, we generate the lightest involutory/ non-involutory MDS matrices known over F23, F24 and F28 in terms of XOR count. In this context, we present new 4 * 4 involutory MDS matrices over F23, F24 and F28, which can be implemented by 13 XOR operations with depth 5, 25 XOR operations with depth 5 and 42 XOR operations with depth 4, respectively. Finally, we denote a new property of Hadamard matrix, i.e., (involutory and MDS) Hadamard matrix form is, in fact, a representative matrix form that can be used to generate a small subset of all 2k * 2k involutory MDS matrices, where k?> 1. For k = 1, Hadamard matrix form can be used to generate all involutory MDS matrices.