November  2019, 13(4): 779-843. doi: 10.3934/amc.2019045

Cryptographically significant mds matrices over finite fields: A brief survey and some generalized results

1. 

Applied Statistics Unit, Indian Statistical Institute, 203, B.T. Road, Kolkata-700108, India

2. 

Ashoka University, Sonepat, Haryana, India

3. 

School of Engineering and Mathematical Sciences, City University London, London EC1V 0HB, United Kingdom

* Corresponding author: Sumit Kumar Pandey

Received  December 2018 Published  June 2019

A matrix is MDS or super-regular if and only if every square submatrices of it are nonsingular. MDS matrices provide perfect diffusion in block ciphers and hash functions. In this paper we provide a brief survey on cryptographically significant MDS matrices - a first to the best of our knowledge. In addition to providing a summary of existing results, we make several contributions. We exhibit some deep and nontrivial interconnections between different constructions of MDS matrices. For example, we prove that all known Vandermonde constructions are basically equivalent to Cauchy constructions. We prove some folklore results which are used in MDS matrix literature. Wherever possible, we provide some simpler alternative proofs. We do not discuss efficiency issues or hardware implementations; however, the theory accumulated and discussed here should provide an easy guide towards efficient implementations.

Citation: Kishan Chand Gupta, Sumit Kumar Pandey, Indranil Ghosh Ray, Susanta Samanta. Cryptographically significant mds matrices over finite fields: A brief survey and some generalized results. Advances in Mathematics of Communications, 2019, 13 (4) : 779-843. doi: 10.3934/amc.2019045
References:
[1]

D. Augot and M. Finiasz, Exhaustive search for small dimension recursive MDS diffusion layers or block ciphers and hash functions, In Proc. of the 2013 IEEE International Symposium on Information Theory, IEEE, 2013, 1551–1555. doi: 10.1109/ISIT.2013.6620487.

[2]

D. Augot and M. Finiasz, Direct construction of recursive mds diffusion layers using shortened BCH codes, In FSE 2014, LNCS, Springer, 8540 (2015), 3–17, Also available http://eprint.iacr.org/2014/566.pdf. doi: 10.1007/978-3-662-46706-0_1.

[3]

P. S. L. M. Barreto and V. Rijmen, The Khazad Legacy-Level Block Cipher, Submission to the NESSIE Project, 2000. Available at https://www.cosic.esat.kuleuven.be/nessie/workshop/submissions.html.

[4]

P. S. L. M. Barreto and V. Rijmen, The Anubis block cipher, Submission to the NESSIE Project, 2000. Available at https://www.cosic.esat.kuleuven.be/nessie/workshop/submissions.html.

[5]

P. S. L. M. Barreto and V. Rijmen, The Whirlpool hashing function, In Proceedings of the 1st NESSIE Workshop, 15 pages, 2000. Available at https://www.cosic.esat.kuleuven.be/nessie/workshop/submissions.html.

[6]

C. Beierle, T. Kranz and G. Leander, Lightweight multiplication in $GF(2^n)$ with applications to MDS matrices, Advances in cryptology–CRYPTO 2016. Part I, 625–653, Lecture Notes in Comput. Sci., 9814, Springer, Berlin, 2016. doi: 10.1007/978-3-662-53018-4_23.

[7]

T. P. Berger, Construction of recursive MDS diffusion layers from gabidulin codes, In INDOCRYPT 2013, LNCS, Springer, 8250 (2013), 274–285. doi: 10.1007/978-3-319-03515-4_18.

[8]

T. P. Berger and A. Ourivski, Construction of new MDS codes from Gabidulin codes, In Proceedings of ACCT 2009, Kranevo, Bulgaria, 40–47, June, 2004.

[9]

W. Bosma, J. Cannon and C. Playoust, The magma algebra system I: The user language, J. Symbolic Comput, 24 (1997), 235–265, Computational algebra and number theory (London, 1993). doi: 10.1006/jsco.1996.0125.

[10]

G. Castagnoli, J. L. Massey, P. A. Schoeller and N. von Seeman, On repeated-root cyclic codes, In IEEE Transactions on Inform. Theory, 37 (1991), 337–342. doi: 10.1109/18.75249.

[11]

V. Cauchois and P. Loidreau, About circulant involutory MDS matrices, Des. Codes Cryptogr., 87 (2019), 249-260.  doi: 10.1007/s10623-018-0520-3.

[12]

J. Choy, H. Yap, K. Khoo, J. Guo, T. Peyrin, A. Poschmann and C. H. Tan, SPN-hash: Improving the provable resistance against differential collision attacks, Progress in cryptology–AFRICACRYPT 2012, 270–286, Lecture Notes in Comput. Sci., 7374, Springer, Heidelberg, 2012. doi: 10.1007/978-3-642-31410-0_17.

[13]

T. Cui, C. Jin and Z. Kong, On compact cauchy matrices for substitution-permutation networks, In IEEE Transactions on Computers, 64 (2015), 2098–2102. doi: 10.1109/TC.2014.2346180.

[14]

J. Daemen, L. R. Knudsen and V. Rijmen, The block cipher SQUARE, In 4th Fast Software Encryption Workshop, LNCS, 1267 (1997), 149–165, Springer-Verlag. doi: 10.1007/BFb0052343.

[15]

J. Daemen and V. Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard, Springer-Verlag, 2002. doi: 10.1007/978-3-662-04722-4.

[16]

G. D. Filho, P. Barreto and V. Rijmen, The Maelstrom-0 Hash Function, In Proceedings of the 6th Brazilian Symposium on Information and Computer Systems Security, 2006.

[17]

P. Gauravaram, L. R. Knudsen, K. Matusiewicz, F. Mendel, C. Rechberger, M. Schlaffer and S. Thomsen, Gr$\phi$stl a SHA-3 Candidate, Submission to NIST, 2008, Available at http://www.groestl.info/.

[18]

R. M. Gray, Toeplitz and Circulant Matrices: A Review Foundations and Trends in Communications and Information Theory, NOW, 2005. doi: 10.1561/0100000006.

[19]

J. Guo, T. Peyrin and A. Poschmann, The PHOTON family of lightweight hash functions, In CRYPTO, Springer, 2011 (2011), 222–239. doi: 10.1007/978-3-642-22792-9_13.

[20]

J. Guo, T. Peyrin, A. Poshmann and M. J. B. Robshaw, The LED block cipher, In CHES 2011, LNCS, 6917 (2011), 326–341, Springer. doi: 10.1007/978-3-642-23951-9_22.

[21]

K. C. Gupta and I. G. Ray, On constructions of involutory MDS matrices, Progress in cryptology–AFRICACRYPT 2013, 7918 (2013), 43–60. doi: 10.1007/978-3-642-38553-7_3.

[22]

K. C. Gupta and I. G. Ray, On constructions of MDS matrices from companion matrices for lightweight cryptography, In CD-ARES 2013 Workshops: MoCrySEn, Springer, 8128 (2013), 29–43. doi: 10.1007/978-3-642-40588-4_3.

[23]

K. C. Gupta and I. G. Ray, On constructions of circulant MDS matrices for lightweight cryptography, In ISPEC 2014, Springer, 2014, 564–576.

[24]

K. C. Gupta and I. G. Ray, Cryptographically significant MDS matrices based on circulant and circulant-like matrices for lightweight applications, Cryptography and Communications, 7 (2015), 257-287.  doi: 10.1007/s12095-014-0116-3.

[25]

K. C. Gupta, S. K. Pandey and A. Venkateswarlu, Towards a general construction of recursive MDS diffusion layers, In WCC2015, https://hal.inria.fr/hal-01276436.

[26]

K. C. Gupta, S. K. Pandey and A. Venkateswarlu, On the direct construction of recursive MDS matrices, In Des. Codes Crypto., 82 (2017), 77–94. doi: 10.1007/s10623-016-0233-4.

[27]

K. C. Gupta, S. K. Pandey and A. Venkateswarlu, Towards a general construction of recursive MDS diffusion layers, In Des. Codes Crypto., 82 (2017), 179–195. doi: 10.1007/s10623-016-0261-0.

[28]

K. C. GuptaS. K. Pandey and A. Venkateswarlu, Almost involutory recursive MDS diffusion layers, Design, Codes and Cryptography, 87 (2019), 609-626.  doi: 10.1007/s10623-018-0582-2.

[29]

H. Han and H. Zhang, The research on the maximum branch number of P-permutations, 2010 2nd International Workshop on Intelligent Systems and Applications, Wuhan, 2010, 1–4. doi: 10.1109/IWISA.2010.5473354.

[30]

H. M. Heys and S. E. Tavares, The design of substitution-permutation networks resistant to differential and linear cryptanalysis, Proceedings of 2nd ACM Conference on Computer and Communications Security, Fairfax, Virginia, 1994, 148–155. doi: 10.1145/191177.191206.

[31]

H. M. Heys and S. E. Tavares, Avalanche characteristics of substitution-permutation encryption networks, IEEE Trans. Comp., 44 (1995), 1131-1139.  doi: 10.1109/12.464391.

[32]

H. M. Heys and S. E. Tavares, The design of product ciphers resistant to differential and linear cryptanalysis, Journal of Cryptology, 9 (1996), 1-19.  doi: 10.1007/BF02254789.

[33]

J. W. P. Hirschfeld, The main conjecture for MDS codes, Cryptography and Coding (Cirencester, 1995),, Lecture Notes in Comput. Sci., 1025 (1995), 44–52. doi: 10.1007/3-540-60693-9_7.

[34]

P. Junod and S. Vaudenay, Perfect diffusion primitives for block ciphers building efficient MDS matrices, Selected Areas in Cryptography, 84–99, Lecture Notes in Comput. Sci., 3357, Springer, Berlin, 2005. doi: 10.1007/978-3-540-30564-4_6.

[35]

P. Junod and S. Vaudenay, FOX: A new family of block ciphers, Selected Areas in Cryptography, 114–129, Lecture Notes in Comput. Sci., 3357, Springer, Berlin, 2005. doi: 10.1007/978-3-540-30564-4_8.

[36]

P. Junod and M. Macchetti, Revisiting the IDEA philosophy, International Workshop on Fast Software Encryption, FSE 2009: Fast Software Encryption, Lecture Notes in Computer Science, 5665 (2009), 277–295. doi: 10.1007/978-3-642-03317-9_17.

[37]

K. Khoo, T. Peyrin, A. Y. Poschmann and H. Yap, FOAM: Searching for hardware-optimal SPN structures and components with a fair comparison, In Lejla Batina and Matthew Robshaw, editors, Cryptographic Hardware and Embedded Systems-CHES 2014, volume 8731 of Lecture Notes in Computer Science, pages 433–450. Springer Berlin Heidelberg, 2014.

[38]

N. Kolokotronis, K. Limniotis and N. Kalouptsidis, Factorization of determinants over finite fields and application in stream ciphers, In Cryptogr. Commun., 1 (2009), 175–205. doi: 10.1007/s12095-008-0005-8.

[39]

I. Kra and S. R. Santiago, On circulant matrices, Notices of the AMS, 59 (2012), 368-377.  doi: 10.1090/noti804.

[40]

J. Lacan and J. Fimes, A construction of matrices with no singular square submatrices, Finite Fields and Applications, 2948 (2004), 145-147.  doi: 10.1007/978-3-540-24633-6_11.

[41]

J. Lacan and J. Fimes, Systematic MDS erasure codes based on vandermonde matrices, IEEE Trans. Commun. Lett., 8 (2004), 570-572.  doi: 10.1109/LCOMM.2004.833807.

[42]

R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 2nd edition, 1997.

[43]

J. H. van Lint, Repeated-Root Cyclic Codes, IEEE Transactions on Inform. Theory, 37 (1991), 343-345.  doi: 10.1109/18.75250.

[44]

M. Liu and S. M. Sim, Lightweight MDS generalized circulant matrices, International Conference on Fast Software Encryption, Lecture Notes in Computer Science, 9783 (2016), 101–120. Springer, Berlin, Heidelberg. doi: 10.1007/978-3-662-52993-5_6.

[45]

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

[46]

F. Mattoussi, V. Roca and B. Sayadi, Complexity comparison of the use of Vandermonde versus Hankel matrices to build systematic MDS Reed-Solomon codes, 2012 IEEE 13th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), Cesme, 2012, 344–348. doi: 10.1109/SPAWC.2012.6292924.

[47]

J. Nakahara and E. Abrahao, A New Involutory MDS Matrix for the AES, International Journal of Network Security, 9 (2009), 109-116. 

[48]

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

[49]

A. R. Rao and P. Bhimasankaram, Linear Algebra, Second Edition, Hindustan Book Agency.

[50]

V. Rijmen, J. Daemen, B. Preneel, A. Bosselaers and E. D. Win, The cipher SHARK, In 3rd Fast Software Encryption Workshop, LNCS, 1039 (1996), 99–111, Springer-Verlag. doi: 10.1007/3-540-60865-6_47.

[51]

R. M. Roth and G. Seroussi, On generator matrices of MDS codes, In IEEE Transactions on Information Theory, 31 (1985), 826–830. doi: 10.1109/TIT.1985.1057113.

[52]

R. M. Roth and A. Lempel, On MDS codes via Cauchy matrices, In IEEE Transactions on Information Theory, 35 (1989), 1314–1319. doi: 10.1109/18.45291.

[53]

M. SajadiehM. DakhilalianH. Mala and B. Omoomi, On construction of involutory MDS matrices from Vandermonde Matrices in $GF(2^q)$, Design, Codes Cryptography, 64 (2012), 287-308.  doi: 10.1007/s10623-011-9578-x.

[54]

M. SajadiehM. DakhilalianH. Mala and P. Sepehrdad, Recursive diffusion layers for block ciphers and hash functions, FSE 2012, 7549 (2012), 385-401.  doi: 10.1007/978-3-642-34047-5_22.

[55]

S. Sarkar and H. Syed, Lightweight diffusion layer: Importance of Toeplitz matrices, IACR Trans. Symmetric Cryptol., 2016 (2016), 95-113. 

[56]

S. Sarkar and H. Syed, Analysis of toeplitz MDS matrices, ACISP 2017, LNCS, 10343 (2017), 3–18. doi: 10.1007/978-3-319-59870-3_1.

[57]

B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall and N. Ferguson, Twofish: A 128-bit block cipher, In the first AES Candidate Conference. National Institute for Standards and Technology, 1998.

[58]

B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall and N. Ferguson, The Twofish encryption algorithm, Wiley, 1999.

[59]

C. Schnorr and S. Vaudenay, Black box cryptanalysis of hash networks based on multipermutations, Advances in cryptology–EUROCRYPT '94 (Perugia), Proceedings, LNCS, Springer-Verlag, 950 (1995), 47–57. doi: 10.1007/BFb0053423.

[60]

C. E. Shannon, Communication theory of secrecy systems, Bell Syst. Technical J., 28 (1949), 656-715.  doi: 10.1002/j.1538-7305.1949.tb00928.x.

[61]

T. Shirai and K. Shibutani, On the diffusion matrix employed in the Whirlpool hashing function, NESSIE public report, 2003. Available at https://www.cosic.esat.kuleuven.be/nessie/reports/phase2/whirlpool-20030311.pdf.

[62]

T. Shirai, K. Shibutani, T. Akishita, S. Moriai and T. Iwata, The 128-Bit blockcipher CLEFIA (Extended Abstract), Fnternational Workshop on Fast Software Encryption, Lecture Notes in Computer Science, 4593 (2017), 181–195, Springer, Berlin, Heidelberg doi: 10.1007/978-3-540-74619-5_12.

[63]

S. M. Sim, K. Khoo, F. Oggier and T. Peyrin, Lightweight MDS Involution Matrices, FSE 2015: Fast Software Encryption, Lecture Notes in Computer Science, 9054 (2015), 471–493. Springer, Berlin, Heidelberg. doi: 10.1007/978-3-662-48116-5_23.

[64]

D. Toh, J. Teo, K. Khoo and S. Sim, Lightweight MDS Serial-Type Matrices with Minimal Fixed XOR Count, In AFRICACRYPT 2018, LNCS, 10831 (2018), 51–71. doi: 10.1007/978-3-319-89339-6_4.

[65]

S. Vaudenay, On the need for multipermutations: Cryptanalysis of MD4 and SAFER, Fast Software Encryption, Proceedings, LNCS, 108 (1995), 286–297. Springer-Verlag, 1995. doi: 10.1007/3-540-60590-8_22.

[66]

D. Watanabe, S. Furuya, H. Yoshida, K. Takaragi and B. Preneel, A new keystream generator MUGI, FSE 2002: Fast Software Encryption, Springer Berlin/Heidelberg, 2365 (2002), 179–194. doi: 10.1007/3-540-45661-9_14.

[67]

S. Wu, M. Wang and W. Wu, Recursive diffusion layers for (lightweight) block ciphers and hash functions, SAC 2012: Selected Areas in Cryptography, LNCS, Springer-Verlag Berlin Heidelberg, 7707 (2013), 355–371. doi: 10.1007/978-3-642-35999-6_23.

[68]

A. M. Youssef, S. E. Tavares and H. M. Heys, A New Class of Substitution Permutation Networks, Workshop on Selected Areas in Cryptography, SAC '96, Workshop Record, (1996), 132–147.

[69]

A. M. Youssef, S. Mister and S. E. Tavares, On the Design of Linear Transformations for Substitution Permutation Encryption Networks, In Workshop On Selected Areas in Cryptography, SAC, 97 (1997), 40–48.

show all references

References:
[1]

D. Augot and M. Finiasz, Exhaustive search for small dimension recursive MDS diffusion layers or block ciphers and hash functions, In Proc. of the 2013 IEEE International Symposium on Information Theory, IEEE, 2013, 1551–1555. doi: 10.1109/ISIT.2013.6620487.

[2]

D. Augot and M. Finiasz, Direct construction of recursive mds diffusion layers using shortened BCH codes, In FSE 2014, LNCS, Springer, 8540 (2015), 3–17, Also available http://eprint.iacr.org/2014/566.pdf. doi: 10.1007/978-3-662-46706-0_1.

[3]

P. S. L. M. Barreto and V. Rijmen, The Khazad Legacy-Level Block Cipher, Submission to the NESSIE Project, 2000. Available at https://www.cosic.esat.kuleuven.be/nessie/workshop/submissions.html.

[4]

P. S. L. M. Barreto and V. Rijmen, The Anubis block cipher, Submission to the NESSIE Project, 2000. Available at https://www.cosic.esat.kuleuven.be/nessie/workshop/submissions.html.

[5]

P. S. L. M. Barreto and V. Rijmen, The Whirlpool hashing function, In Proceedings of the 1st NESSIE Workshop, 15 pages, 2000. Available at https://www.cosic.esat.kuleuven.be/nessie/workshop/submissions.html.

[6]

C. Beierle, T. Kranz and G. Leander, Lightweight multiplication in $GF(2^n)$ with applications to MDS matrices, Advances in cryptology–CRYPTO 2016. Part I, 625–653, Lecture Notes in Comput. Sci., 9814, Springer, Berlin, 2016. doi: 10.1007/978-3-662-53018-4_23.

[7]

T. P. Berger, Construction of recursive MDS diffusion layers from gabidulin codes, In INDOCRYPT 2013, LNCS, Springer, 8250 (2013), 274–285. doi: 10.1007/978-3-319-03515-4_18.

[8]

T. P. Berger and A. Ourivski, Construction of new MDS codes from Gabidulin codes, In Proceedings of ACCT 2009, Kranevo, Bulgaria, 40–47, June, 2004.

[9]

W. Bosma, J. Cannon and C. Playoust, The magma algebra system I: The user language, J. Symbolic Comput, 24 (1997), 235–265, Computational algebra and number theory (London, 1993). doi: 10.1006/jsco.1996.0125.

[10]

G. Castagnoli, J. L. Massey, P. A. Schoeller and N. von Seeman, On repeated-root cyclic codes, In IEEE Transactions on Inform. Theory, 37 (1991), 337–342. doi: 10.1109/18.75249.

[11]

V. Cauchois and P. Loidreau, About circulant involutory MDS matrices, Des. Codes Cryptogr., 87 (2019), 249-260.  doi: 10.1007/s10623-018-0520-3.

[12]

J. Choy, H. Yap, K. Khoo, J. Guo, T. Peyrin, A. Poschmann and C. H. Tan, SPN-hash: Improving the provable resistance against differential collision attacks, Progress in cryptology–AFRICACRYPT 2012, 270–286, Lecture Notes in Comput. Sci., 7374, Springer, Heidelberg, 2012. doi: 10.1007/978-3-642-31410-0_17.

[13]

T. Cui, C. Jin and Z. Kong, On compact cauchy matrices for substitution-permutation networks, In IEEE Transactions on Computers, 64 (2015), 2098–2102. doi: 10.1109/TC.2014.2346180.

[14]

J. Daemen, L. R. Knudsen and V. Rijmen, The block cipher SQUARE, In 4th Fast Software Encryption Workshop, LNCS, 1267 (1997), 149–165, Springer-Verlag. doi: 10.1007/BFb0052343.

[15]

J. Daemen and V. Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard, Springer-Verlag, 2002. doi: 10.1007/978-3-662-04722-4.

[16]

G. D. Filho, P. Barreto and V. Rijmen, The Maelstrom-0 Hash Function, In Proceedings of the 6th Brazilian Symposium on Information and Computer Systems Security, 2006.

[17]

P. Gauravaram, L. R. Knudsen, K. Matusiewicz, F. Mendel, C. Rechberger, M. Schlaffer and S. Thomsen, Gr$\phi$stl a SHA-3 Candidate, Submission to NIST, 2008, Available at http://www.groestl.info/.

[18]

R. M. Gray, Toeplitz and Circulant Matrices: A Review Foundations and Trends in Communications and Information Theory, NOW, 2005. doi: 10.1561/0100000006.

[19]

J. Guo, T. Peyrin and A. Poschmann, The PHOTON family of lightweight hash functions, In CRYPTO, Springer, 2011 (2011), 222–239. doi: 10.1007/978-3-642-22792-9_13.

[20]

J. Guo, T. Peyrin, A. Poshmann and M. J. B. Robshaw, The LED block cipher, In CHES 2011, LNCS, 6917 (2011), 326–341, Springer. doi: 10.1007/978-3-642-23951-9_22.

[21]

K. C. Gupta and I. G. Ray, On constructions of involutory MDS matrices, Progress in cryptology–AFRICACRYPT 2013, 7918 (2013), 43–60. doi: 10.1007/978-3-642-38553-7_3.

[22]

K. C. Gupta and I. G. Ray, On constructions of MDS matrices from companion matrices for lightweight cryptography, In CD-ARES 2013 Workshops: MoCrySEn, Springer, 8128 (2013), 29–43. doi: 10.1007/978-3-642-40588-4_3.

[23]

K. C. Gupta and I. G. Ray, On constructions of circulant MDS matrices for lightweight cryptography, In ISPEC 2014, Springer, 2014, 564–576.

[24]

K. C. Gupta and I. G. Ray, Cryptographically significant MDS matrices based on circulant and circulant-like matrices for lightweight applications, Cryptography and Communications, 7 (2015), 257-287.  doi: 10.1007/s12095-014-0116-3.

[25]

K. C. Gupta, S. K. Pandey and A. Venkateswarlu, Towards a general construction of recursive MDS diffusion layers, In WCC2015, https://hal.inria.fr/hal-01276436.

[26]

K. C. Gupta, S. K. Pandey and A. Venkateswarlu, On the direct construction of recursive MDS matrices, In Des. Codes Crypto., 82 (2017), 77–94. doi: 10.1007/s10623-016-0233-4.

[27]

K. C. Gupta, S. K. Pandey and A. Venkateswarlu, Towards a general construction of recursive MDS diffusion layers, In Des. Codes Crypto., 82 (2017), 179–195. doi: 10.1007/s10623-016-0261-0.

[28]

K. C. GuptaS. K. Pandey and A. Venkateswarlu, Almost involutory recursive MDS diffusion layers, Design, Codes and Cryptography, 87 (2019), 609-626.  doi: 10.1007/s10623-018-0582-2.

[29]

H. Han and H. Zhang, The research on the maximum branch number of P-permutations, 2010 2nd International Workshop on Intelligent Systems and Applications, Wuhan, 2010, 1–4. doi: 10.1109/IWISA.2010.5473354.

[30]

H. M. Heys and S. E. Tavares, The design of substitution-permutation networks resistant to differential and linear cryptanalysis, Proceedings of 2nd ACM Conference on Computer and Communications Security, Fairfax, Virginia, 1994, 148–155. doi: 10.1145/191177.191206.

[31]

H. M. Heys and S. E. Tavares, Avalanche characteristics of substitution-permutation encryption networks, IEEE Trans. Comp., 44 (1995), 1131-1139.  doi: 10.1109/12.464391.

[32]

H. M. Heys and S. E. Tavares, The design of product ciphers resistant to differential and linear cryptanalysis, Journal of Cryptology, 9 (1996), 1-19.  doi: 10.1007/BF02254789.

[33]

J. W. P. Hirschfeld, The main conjecture for MDS codes, Cryptography and Coding (Cirencester, 1995),, Lecture Notes in Comput. Sci., 1025 (1995), 44–52. doi: 10.1007/3-540-60693-9_7.

[34]

P. Junod and S. Vaudenay, Perfect diffusion primitives for block ciphers building efficient MDS matrices, Selected Areas in Cryptography, 84–99, Lecture Notes in Comput. Sci., 3357, Springer, Berlin, 2005. doi: 10.1007/978-3-540-30564-4_6.

[35]

P. Junod and S. Vaudenay, FOX: A new family of block ciphers, Selected Areas in Cryptography, 114–129, Lecture Notes in Comput. Sci., 3357, Springer, Berlin, 2005. doi: 10.1007/978-3-540-30564-4_8.

[36]

P. Junod and M. Macchetti, Revisiting the IDEA philosophy, International Workshop on Fast Software Encryption, FSE 2009: Fast Software Encryption, Lecture Notes in Computer Science, 5665 (2009), 277–295. doi: 10.1007/978-3-642-03317-9_17.

[37]

K. Khoo, T. Peyrin, A. Y. Poschmann and H. Yap, FOAM: Searching for hardware-optimal SPN structures and components with a fair comparison, In Lejla Batina and Matthew Robshaw, editors, Cryptographic Hardware and Embedded Systems-CHES 2014, volume 8731 of Lecture Notes in Computer Science, pages 433–450. Springer Berlin Heidelberg, 2014.

[38]

N. Kolokotronis, K. Limniotis and N. Kalouptsidis, Factorization of determinants over finite fields and application in stream ciphers, In Cryptogr. Commun., 1 (2009), 175–205. doi: 10.1007/s12095-008-0005-8.

[39]

I. Kra and S. R. Santiago, On circulant matrices, Notices of the AMS, 59 (2012), 368-377.  doi: 10.1090/noti804.

[40]

J. Lacan and J. Fimes, A construction of matrices with no singular square submatrices, Finite Fields and Applications, 2948 (2004), 145-147.  doi: 10.1007/978-3-540-24633-6_11.

[41]

J. Lacan and J. Fimes, Systematic MDS erasure codes based on vandermonde matrices, IEEE Trans. Commun. Lett., 8 (2004), 570-572.  doi: 10.1109/LCOMM.2004.833807.

[42]

R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 2nd edition, 1997.

[43]

J. H. van Lint, Repeated-Root Cyclic Codes, IEEE Transactions on Inform. Theory, 37 (1991), 343-345.  doi: 10.1109/18.75250.

[44]

M. Liu and S. M. Sim, Lightweight MDS generalized circulant matrices, International Conference on Fast Software Encryption, Lecture Notes in Computer Science, 9783 (2016), 101–120. Springer, Berlin, Heidelberg. doi: 10.1007/978-3-662-52993-5_6.

[45]

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

[46]

F. Mattoussi, V. Roca and B. Sayadi, Complexity comparison of the use of Vandermonde versus Hankel matrices to build systematic MDS Reed-Solomon codes, 2012 IEEE 13th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), Cesme, 2012, 344–348. doi: 10.1109/SPAWC.2012.6292924.

[47]

J. Nakahara and E. Abrahao, A New Involutory MDS Matrix for the AES, International Journal of Network Security, 9 (2009), 109-116. 

[48]

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

[49]

A. R. Rao and P. Bhimasankaram, Linear Algebra, Second Edition, Hindustan Book Agency.

[50]

V. Rijmen, J. Daemen, B. Preneel, A. Bosselaers and E. D. Win, The cipher SHARK, In 3rd Fast Software Encryption Workshop, LNCS, 1039 (1996), 99–111, Springer-Verlag. doi: 10.1007/3-540-60865-6_47.

[51]

R. M. Roth and G. Seroussi, On generator matrices of MDS codes, In IEEE Transactions on Information Theory, 31 (1985), 826–830. doi: 10.1109/TIT.1985.1057113.

[52]

R. M. Roth and A. Lempel, On MDS codes via Cauchy matrices, In IEEE Transactions on Information Theory, 35 (1989), 1314–1319. doi: 10.1109/18.45291.

[53]

M. SajadiehM. DakhilalianH. Mala and B. Omoomi, On construction of involutory MDS matrices from Vandermonde Matrices in $GF(2^q)$, Design, Codes Cryptography, 64 (2012), 287-308.  doi: 10.1007/s10623-011-9578-x.

[54]

M. SajadiehM. DakhilalianH. Mala and P. Sepehrdad, Recursive diffusion layers for block ciphers and hash functions, FSE 2012, 7549 (2012), 385-401.  doi: 10.1007/978-3-642-34047-5_22.

[55]

S. Sarkar and H. Syed, Lightweight diffusion layer: Importance of Toeplitz matrices, IACR Trans. Symmetric Cryptol., 2016 (2016), 95-113. 

[56]

S. Sarkar and H. Syed, Analysis of toeplitz MDS matrices, ACISP 2017, LNCS, 10343 (2017), 3–18. doi: 10.1007/978-3-319-59870-3_1.

[57]

B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall and N. Ferguson, Twofish: A 128-bit block cipher, In the first AES Candidate Conference. National Institute for Standards and Technology, 1998.

[58]

B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall and N. Ferguson, The Twofish encryption algorithm, Wiley, 1999.

[59]

C. Schnorr and S. Vaudenay, Black box cryptanalysis of hash networks based on multipermutations, Advances in cryptology–EUROCRYPT '94 (Perugia), Proceedings, LNCS, Springer-Verlag, 950 (1995), 47–57. doi: 10.1007/BFb0053423.

[60]

C. E. Shannon, Communication theory of secrecy systems, Bell Syst. Technical J., 28 (1949), 656-715.  doi: 10.1002/j.1538-7305.1949.tb00928.x.

[61]

T. Shirai and K. Shibutani, On the diffusion matrix employed in the Whirlpool hashing function, NESSIE public report, 2003. Available at https://www.cosic.esat.kuleuven.be/nessie/reports/phase2/whirlpool-20030311.pdf.

[62]

T. Shirai, K. Shibutani, T. Akishita, S. Moriai and T. Iwata, The 128-Bit blockcipher CLEFIA (Extended Abstract), Fnternational Workshop on Fast Software Encryption, Lecture Notes in Computer Science, 4593 (2017), 181–195, Springer, Berlin, Heidelberg doi: 10.1007/978-3-540-74619-5_12.

[63]

S. M. Sim, K. Khoo, F. Oggier and T. Peyrin, Lightweight MDS Involution Matrices, FSE 2015: Fast Software Encryption, Lecture Notes in Computer Science, 9054 (2015), 471–493. Springer, Berlin, Heidelberg. doi: 10.1007/978-3-662-48116-5_23.

[64]

D. Toh, J. Teo, K. Khoo and S. Sim, Lightweight MDS Serial-Type Matrices with Minimal Fixed XOR Count, In AFRICACRYPT 2018, LNCS, 10831 (2018), 51–71. doi: 10.1007/978-3-319-89339-6_4.

[65]

S. Vaudenay, On the need for multipermutations: Cryptanalysis of MD4 and SAFER, Fast Software Encryption, Proceedings, LNCS, 108 (1995), 286–297. Springer-Verlag, 1995. doi: 10.1007/3-540-60590-8_22.

[66]

D. Watanabe, S. Furuya, H. Yoshida, K. Takaragi and B. Preneel, A new keystream generator MUGI, FSE 2002: Fast Software Encryption, Springer Berlin/Heidelberg, 2365 (2002), 179–194. doi: 10.1007/3-540-45661-9_14.

[67]

S. Wu, M. Wang and W. Wu, Recursive diffusion layers for (lightweight) block ciphers and hash functions, SAC 2012: Selected Areas in Cryptography, LNCS, Springer-Verlag Berlin Heidelberg, 7707 (2013), 355–371. doi: 10.1007/978-3-642-35999-6_23.

[68]

A. M. Youssef, S. E. Tavares and H. M. Heys, A New Class of Substitution Permutation Networks, Workshop on Selected Areas in Cryptography, SAC '96, Workshop Record, (1996), 132–147.

[69]

A. M. Youssef, S. Mister and S. E. Tavares, On the Design of Linear Transformations for Substitution Permutation Encryption Networks, In Workshop On Selected Areas in Cryptography, SAC, 97 (1997), 40–48.

Table 1.  Comparison between Vandermonde and Cauchy based constructions of MDS matrices over a finite field
Construction Type Vandermonde based Construction
$ V_1^{-1}V_2 $ and $ V_2^{-1}V_1 $
Cauchy based Construction
$ M $
Type 1: No extra condition 1. Need not be involutory
2. Need not be Hadamard
3. Need not be compact
1. Need not be involutory
2. Need not be Hadamard
3. Need not be compact
Type 2: $ y_i=l+x_i $, where $ l $ is an arbitrary nonzero element in $ \mathbb{F}_{2^r} $ 1. Involutory and equal
2. Need not be Hadamard
3. Need not be compact
1. Need not be involutory, whereas $ D_1MD_2 $ is involutory for some nonsingular diagonal matrices $ D_1 $ and $ D_2 $ (see Remark 21)
2. Need not be Hadamard
3. Need not be compact
Type 3: $ x_i $'s are the elements of an additive subgroup $ G=\{x_0,x_1,x_2,\dots,x_{n-1}\} $ of order $ n $ of $ \mathbb{F}_{2^r} $ and $ l \not \in G $ 1. Involutory and equal
2. Need not be Hadamard
3. Compact
1. Need not be involutory, whereas $ \frac{1}{c}M $ is involutory, where c is the sum of the elements of any row
2. Need not be Hadamard
3. Compact
Type 4: $ x_i $'s are the elements of an additive subgroup $ G=\{x_0,x_1,x_2,\dots,x_{n-1}\} $ of order $ n $ of $ \mathbb{F}_{2^r} $ such that $ x_i+x_j=x_{i \oplus j} $ and $ l \not \in G $ 1. Involutory and equal
2. Hadamard
3. Compact
1. Need not be involutory, whereas $ \frac{1}{c}M $ is involutory, where c is the sum of the elements of any row
2. Hadamard
3. Compact
Construction Type Vandermonde based Construction
$ V_1^{-1}V_2 $ and $ V_2^{-1}V_1 $
Cauchy based Construction
$ M $
Type 1: No extra condition 1. Need not be involutory
2. Need not be Hadamard
3. Need not be compact
1. Need not be involutory
2. Need not be Hadamard
3. Need not be compact
Type 2: $ y_i=l+x_i $, where $ l $ is an arbitrary nonzero element in $ \mathbb{F}_{2^r} $ 1. Involutory and equal
2. Need not be Hadamard
3. Need not be compact
1. Need not be involutory, whereas $ D_1MD_2 $ is involutory for some nonsingular diagonal matrices $ D_1 $ and $ D_2 $ (see Remark 21)
2. Need not be Hadamard
3. Need not be compact
Type 3: $ x_i $'s are the elements of an additive subgroup $ G=\{x_0,x_1,x_2,\dots,x_{n-1}\} $ of order $ n $ of $ \mathbb{F}_{2^r} $ and $ l \not \in G $ 1. Involutory and equal
2. Need not be Hadamard
3. Compact
1. Need not be involutory, whereas $ \frac{1}{c}M $ is involutory, where c is the sum of the elements of any row
2. Need not be Hadamard
3. Compact
Type 4: $ x_i $'s are the elements of an additive subgroup $ G=\{x_0,x_1,x_2,\dots,x_{n-1}\} $ of order $ n $ of $ \mathbb{F}_{2^r} $ such that $ x_i+x_j=x_{i \oplus j} $ and $ l \not \in G $ 1. Involutory and equal
2. Hadamard
3. Compact
1. Need not be involutory, whereas $ \frac{1}{c}M $ is involutory, where c is the sum of the elements of any row
2. Hadamard
3. Compact
Table 2.  Several results of Circulant, Circulant-like, left-circulant, Toeplitz and Hankel matrices over a finite field
Type Dimension Involutory MDS Orthogonal MDS
Circulant $ 2^n \times 2^n $ do not exist do not exist
$ 2n \times 2n $ do not exist may exist (Remark 24)
$ (2n+1) \times (2n+1) $ do not exist may exist (Remark 24)
Type-Ⅰ $ 2n \times 2n $ do not exist do not exist
$ (2n+1) \times (2n+1) $ do not exist do not exist
Type-Ⅱ $ 2(2n) \times 2(2n) $ do not exist do not exist
$ 2(2n+1) \times 2(2n+1) $ may exist (Example 9) may exist
left-Circulant $ 2^n \times 2^n $ do not exist do not exist
$ 2n \times 2n $ may exist (Remark 31) may exist (Remark 31)
$ (2n+1) \times (2n+1) $ may exist (Remark 31) may exist (Remark 31)
Toeplitz $ 2^n \times 2^n $ do not exist do not exist
$ 2n \times 2n $ do not exist may exist (Remark 34)
$ (2n+1) \times (2n+1) $ do not exist may exist (Remark 34)
Hankel $ 2^n \times 2^n $ do not exist do not exist
$ 2n \times 2n $ may exist (Remark 36) may exist (Remark 36)
$ (2n+1) \times (2n+1) $ may exist (Remark 36) may exist (Remark 36)
Type Dimension Involutory MDS Orthogonal MDS
Circulant $ 2^n \times 2^n $ do not exist do not exist
$ 2n \times 2n $ do not exist may exist (Remark 24)
$ (2n+1) \times (2n+1) $ do not exist may exist (Remark 24)
Type-Ⅰ $ 2n \times 2n $ do not exist do not exist
$ (2n+1) \times (2n+1) $ do not exist do not exist
Type-Ⅱ $ 2(2n) \times 2(2n) $ do not exist do not exist
$ 2(2n+1) \times 2(2n+1) $ may exist (Example 9) may exist
left-Circulant $ 2^n \times 2^n $ do not exist do not exist
$ 2n \times 2n $ may exist (Remark 31) may exist (Remark 31)
$ (2n+1) \times (2n+1) $ may exist (Remark 31) may exist (Remark 31)
Toeplitz $ 2^n \times 2^n $ do not exist do not exist
$ 2n \times 2n $ do not exist may exist (Remark 34)
$ (2n+1) \times (2n+1) $ do not exist may exist (Remark 34)
Hankel $ 2^n \times 2^n $ do not exist do not exist
$ 2n \times 2n $ may exist (Remark 36) may exist (Remark 36)
$ (2n+1) \times (2n+1) $ may exist (Remark 36) may exist (Remark 36)
[1]

K. T. Arasu, Manil T. Mohan. Optimization problems with orthogonal matrix constraints. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 413-440. doi: 10.3934/naco.2018026

[2]

Meijuan Shang, Yanan Liu, Lingchen Kong, Xianchao Xiu, Ying Yang. Nonconvex mixed matrix minimization. Mathematical Foundations of Computing, 2019, 2 (2) : 107-126. doi: 10.3934/mfc.2019009

[3]

Paul Skerritt, Cornelia Vizman. Dual pairs for matrix groups. Journal of Geometric Mechanics, 2019, 11 (2) : 255-275. doi: 10.3934/jgm.2019014

[4]

Adel Alahmadi, Hamed Alsulami, S.K. Jain, Efim Zelmanov. On matrix wreath products of algebras. Electronic Research Announcements, 2017, 24: 78-86. doi: 10.3934/era.2017.24.009

[5]

Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015

[6]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012

[7]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012

[8]

Henry Adams, Lara Kassab, Deanna Needell. An adaptation for iterative structured matrix completion. Foundations of Data Science, 2021, 3 (4) : 769-791. doi: 10.3934/fods.2021028

[9]

Stefan Possanner, Claudia Negulescu. Diffusion limit of a generalized matrix Boltzmann equation for spin-polarized transport. Kinetic and Related Models, 2011, 4 (4) : 1159-1191. doi: 10.3934/krm.2011.4.1159

[10]

El Mustapha Ait Ben Hassi, Mohamed Fadili, Lahcen Maniar. Controllability of a system of degenerate parabolic equations with non-diagonalizable diffusion matrix. Mathematical Control and Related Fields, 2020, 10 (3) : 623-642. doi: 10.3934/mcrf.2020013

[11]

Lei Zhang, Anfu Zhu, Aiguo Wu, Lingling Lv. Parametric solutions to the regulator-conjugate matrix equations. Journal of Industrial and Management Optimization, 2017, 13 (2) : 623-631. doi: 10.3934/jimo.2016036

[12]

Heide Gluesing-Luerssen, Fai-Lung Tsang. A matrix ring description for cyclic convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 55-81. doi: 10.3934/amc.2008.2.55

[13]

Houduo Qi, ZHonghang Xia, Guangming Xing. An application of the nearest correlation matrix on web document classification. Journal of Industrial and Management Optimization, 2007, 3 (4) : 701-713. doi: 10.3934/jimo.2007.3.701

[14]

Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103

[15]

Li Zhang, Xiaofeng Zhou, Min Chen. The research on the properties of Fourier matrix and bent function. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 571-578. doi: 10.3934/naco.2020052

[16]

Angelo B. Mingarelli. Nonlinear functionals in oscillation theory of matrix differential systems. Communications on Pure and Applied Analysis, 2004, 3 (1) : 75-84. doi: 10.3934/cpaa.2004.3.75

[17]

A. Cibotarica, Jiu Ding, J. Kolibal, Noah H. Rhee. Solutions of the Yang-Baxter matrix equation for an idempotent. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 347-352. doi: 10.3934/naco.2013.3.347

[18]

Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems and Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025

[19]

Leda Bucciantini, Angiolo Farina, Antonio Fasano. Flows in porous media with erosion of the solid matrix. Networks and Heterogeneous Media, 2010, 5 (1) : 63-95. doi: 10.3934/nhm.2010.5.63

[20]

Debasisha Mishra. Matrix group monotonicity using a dominance notion. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 267-274. doi: 10.3934/naco.2015.5.267

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (1962)
  • HTML views (759)
  • Cited by (4)

[Back to Top]