Skip to main content
SpringerLink
Log in

A systematic construction approach for all \(4\times 4\) involutory MDS matrices

  • Original Research
  • Published:
Journal of Applied Mathematics and Computing Aims and scope Submit manuscript

A Correction to this article was published on 03 July 2024

This article has been updated

Abstract

Maximum distance separable (MDS) matrices play a crucial role not only in coding theory but also in the design of block ciphers and hash functions. Of particular interest are involutory MDS matrices, which facilitate the use of a single circuit for both encryption and decryption in hardware implementations. In this article, we present several characterizations of involutory MDS matrices of even order. Additionally, we introduce a new matrix form for obtaining all involutory MDS matrices of even order and compare it with other matrix forms available in the literature. We then propose a technique to systematically construct all \(4 \times 4\) involutory MDS matrices over a finite field \(\mathbb {F}_{2^m}\). This method significantly reduces the search space by focusing on involutory MDS class representative matrices, leading to the generation of all such matrices within a substantially smaller set compared to considering all \(4 \times 4\) involutory matrices. Specifically, our approach involves searching for these representative matrices within a set of cardinality \((2^m-1)^5\). Through this method, we provide an explicit enumeration of the total number of \(4 \times 4\) involutory MDS matrices over \(\mathbb {F}_{2^m}\) for \(m=3,4,\ldots ,8\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1

Similar content being viewed by others

Change history

Notes

  1. \(\mathcal {L}_{2n}\) denotes the set of \(2n \times 2n\) matrices over \(\mathbb {F}_{2^m}\) of type \(\begin{pmatrix} A &{}B\\ C &{}D \end{pmatrix}\), where A, B, C, D are \(n \times n\) non-singular matrices.

References

  1. Daemen, J., Rijmen, V.: The design of Rijndael: AES-the advanced encryption standard. In: Information Security and Cryptography, Springer (2002)

  2. Filho, D.L.G., Barreto, P.S.L.M., Rijmen, V.: The Maelstrom-0 hash function. In: Proceedings of the 6th Brazilian Symposium on Information and Computer Systems Security, pp. 17–29 (2006)

  3. Gauravaram, P., Knudsen, L., Matusiewicz, K., Mendel, F., Rechberger, C., Schläffer, M., Thomsen, S.: Grøstl-a SHA-3 candidate. Submission to NIST (2008) http://www.groestl.info/

  4. Guo, J., Peyrin, T., Poschmann, A.: The PHOTON family of lightweight hash functions. In: Rogaway, P. (ed) Advances in Cryptology—CRYPTO 2011, pp. 222–239. Springer, Berlin, Heidelberg (2011)

  5. Gupta, K.C., Pandey, S.K., Samanta, S.: On the direct construction of MDS and near-MDS matrices. arXiv: 2306.12848 (2023)

  6. Gupta, K.C., Ray, I.G.: On constructions of involutory MDS matrices. In: International Conference on Cryptology in Africa, pp. 43–60. Springer (2013)

  7. Gupta, K.C., Ray, I.G.: Cryptographically significant MDS matrices based on circulant and circulant-like matrices for lightweight applications. Cryptogr. Commun. 7, 257–287 (2015)

  8. Güzel, G.G., Sakalli, M.T., Akleylek, S., Rijmen, V., Çengellenmiş, Y.: A new matrix form to generate all \(3 \times 3\) involutory MDS matrices over \(\mathbb{F} _{2^m}\). Inf. Process. Lett. 147, 61–6 (2019)

    Article  Google Scholar 

  9. Kumar, Y., Mishra, P.R., Samanta, S., Gupta, K.C., Gaur, A.: Construction of all MDS and involutory MDS matrices. arXiv:2403.10372, https://doi.org/10.48550/arXiv.2403.10372 (2024)

  10. Lacan, J., Fimes, J.: A construction of matrices with no singular square submatrices. In: Mullen, G.L., Poli, A., Stichtenoth, H. (ed) Finite Fields and Applications, pp. 145–147. Springer, Berlin, Heidelberg (2004)

  11. Liu, M., Sim, S.M.: Lightweight MDS generalized circulant matrices. In: Peyrin, T. (ed) Fast Software Encryption, pp. 101–120. Springer, Berlin, Heidelberg (2016)

  12. MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes. North-Holland Publishing Co., Amsterdam, New York, Oxford (1977)

    Google Scholar 

  13. Pehlivanoğlu, M. K., Sakalli, M. T., Akleylek, S., Duru, N., Rijmen, V.: Generalisation of Hadamard matrix to generate involutory MDS matrices for lightweight cryptography. IET Information Security 12(4), 348–355 (2018)

  14. Roth, R.M., Lempel, A.: On MDS codes via Cauchy matrices. IEEE Trans. Inf. Theory 35(6), 1314–1319 (1989)

    Article  MathSciNet  Google Scholar 

  15. Sajadieh, M., Dakhilalian, M., Mala, H., Omoomi, B.: On construction of involutory MDS matrices from vandermonde matrices in \(GF(2^q)\). Des. Codes Crypt. 64(3), 287–308 (2012)

    Article  Google Scholar 

  16. Sakalli, M.T., Akleylek, S., Akkanat, K., Rijmen, V.: On the automorphisms and isomorphisms of MDS matrices and their efficient implementations. Turk. J. Electr. Eng. Comput. Sci. 28(1), 275–287 (2020)

    Article  Google Scholar 

  17. Samanta, S.: On the counting of involutory MDS matrices. arXiv: 2310.00090https://doi.org/10.48550/arXiv.2310.00090 (2023)

  18. Sarkar, S., Syed, H.: Lightweight diffusion layer: importance of Toeplitz matrices. IACR Trans. Symm. Cryptol. 2016(1), 95–113 (2016)

    Article  Google Scholar 

  19. Shannon, C.E.: Communication theory of secrecy systems. Bell Syst. Tech. J. 28(4), 656–715 (1949)

    Article  MathSciNet  Google Scholar 

  20. Sim, S.M., Khoo, K., Oggier, F., Peyrin, T.: Lightweight MDS involution matrices. In: Leander, G. (ed) Fast Software Encryption, pp. 471–493. Springer, Berlin, Heidelberg (2015)

  21. Tuncay, G., Sakalli, F.B., Pehlivanoğlu, M.K., Yilmazgüç, G.G., Akleylek, S., Sakalli, M.T.: A new hybrid method combining search and direct based construction ideas to generate all \(4\times 4\) involutory maximum distance separable (MDS) matrices over binary field extensions. PeerJ Comput. Sci. 9, e1577 (2023)

  22. Watanabe, D., Furuya, S., Yoshida, H., Takaragi, K., Preneel, B.: A new keystream generator MUGI. In: Daemen, J., Rijmen, V. (ed) Fast Software Encryption, pp. 179–194. Springer, Berlin, Heidelberg (2002)

  23. Yang, Y., Zeng, X., Wang, S.: Construction of lightweight involutory MDS matrices. Des. Codes Crypt. 89(7), 1453–1483 (2021)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Scientific Analysis Group, DRDO, Metcalfe House Complex, Delhi, 110054, India

    Yogesh Kumar & P. R. Mishra

  2. R. C. Bose Centre for Cryptology and Security, Indian Statistical Institute, Kolkata, 700108, India

    Susanta Samanta

  3. Department of Mathematics, University of Delhi, Delhi, 110007, India

    Atul Gaur

Authors
  1. Yogesh Kumar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. R. Mishra
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Susanta Samanta
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Atul Gaur
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to P. R. Mishra.

Ethics declarations

Conflict of interest

The authors declare that they have no Conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kumar, Y., Mishra, P.R., Samanta, S. et al. A systematic construction approach for all \(4\times 4\) involutory MDS matrices. J. Appl. Math. Comput. 70, 4677–4697 (2024). https://doi.org/10.1007/s12190-024-02142-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12190-024-02142-z

Keywords

Search

Navigation