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

Kishan Chand Gupta; Sumit Kumar Pandey; Indranil Ghosh Ray; Susanta Samanta

doi:10.3934/amc.2019045

Previous Article
AMC Home
This Issue
Next Article
Identity-based key aggregate cryptosystem from multilinear maps

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

Kishan Chand Gupta ^1, , Sumit Kumar Pandey ^2,, , Indranil Ghosh Ray ^3, and Susanta Samanta ^1,

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.

Keywords: Diffusion, involutory matrix, MDS matrix, orthogonal matrix, branch number, Cauchy matrix, Vandermonde matrix.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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/. Google Scholar
[18]	R. M. Gray, Toeplitz and Circulant Matrices: A Review Foundations and Trends in Communications and Information Theory, NOW, 2005. doi: 10.1561/0100000006. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[23]	K. C. Gupta and I. G. Ray, On constructions of circulant MDS matrices for lightweight cryptography, In ISPEC 2014, Springer, 2014, 564–576. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[28]	K. C. Gupta, S. 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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[39]	I. Kra and S. R. Santiago, On circulant matrices, Notices of the AMS, 59 (2012), 368-377. doi: 10.1090/noti804. Google Scholar
[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. Google Scholar
[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. Google Scholar
[42]	R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 2nd edition, 1997. Google Scholar
[43]	J. H. van Lint, Repeated-Root Cyclic Codes, IEEE Transactions on Inform. Theory, 37 (1991), 343-345. doi: 10.1109/18.75250. Google Scholar
[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. Google Scholar
[45]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. Google Scholar
[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. Google Scholar
[47]	J. Nakahara and E. Abrahao, A New Involutory MDS Matrix for the AES, International Journal of Network Security, 9 (2009), 109-116. Google Scholar
[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. Google Scholar
[49]	A. R. Rao and P. Bhimasankaram, Linear Algebra, Second Edition, Hindustan Book Agency. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[53]	M. Sajadieh, M. Dakhilalian, H. 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. Google Scholar
[54]	M. Sajadieh, M. Dakhilalian, H. 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. Google Scholar
[55]	S. Sarkar and H. Syed, Lightweight diffusion layer: Importance of Toeplitz matrices, IACR Trans. Symmetric Cryptol., 2016 (2016), 95-113. Google Scholar
[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. Google Scholar
[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. Google Scholar
[58]	B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall and N. Ferguson, The Twofish encryption algorithm, Wiley, 1999. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar

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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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/. Google Scholar
[18]	R. M. Gray, Toeplitz and Circulant Matrices: A Review Foundations and Trends in Communications and Information Theory, NOW, 2005. doi: 10.1561/0100000006. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[23]	K. C. Gupta and I. G. Ray, On constructions of circulant MDS matrices for lightweight cryptography, In ISPEC 2014, Springer, 2014, 564–576. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[28]	K. C. Gupta, S. 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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[39]	I. Kra and S. R. Santiago, On circulant matrices, Notices of the AMS, 59 (2012), 368-377. doi: 10.1090/noti804. Google Scholar
[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. Google Scholar
[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. Google Scholar
[42]	R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 2nd edition, 1997. Google Scholar
[43]	J. H. van Lint, Repeated-Root Cyclic Codes, IEEE Transactions on Inform. Theory, 37 (1991), 343-345. doi: 10.1109/18.75250. Google Scholar
[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. Google Scholar
[45]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. Google Scholar
[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. Google Scholar
[47]	J. Nakahara and E. Abrahao, A New Involutory MDS Matrix for the AES, International Journal of Network Security, 9 (2009), 109-116. Google Scholar
[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. Google Scholar
[49]	A. R. Rao and P. Bhimasankaram, Linear Algebra, Second Edition, Hindustan Book Agency. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[53]	M. Sajadieh, M. Dakhilalian, H. 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. Google Scholar
[54]	M. Sajadieh, M. Dakhilalian, H. 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. Google Scholar
[55]	S. Sarkar and H. Syed, Lightweight diffusion layer: Importance of Toeplitz matrices, IACR Trans. Symmetric Cryptol., 2016 (2016), 95-113. Google Scholar
[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. Google Scholar
[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. Google Scholar
[58]	B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall and N. Ferguson, The Twofish encryption algorithm, Wiley, 1999. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar

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

Table Options

Download as excel

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
Type-Ⅰ	$ (2n+1) \times (2n+1) $	do not exist	do not exist
Type-Ⅱ	$ 2(2n) \times 2(2n) $	do not exist	do not exist
Type-Ⅱ	$ 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)

Table Options

Download as excel

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
Type-Ⅰ	$ (2n+1) \times (2n+1) $	do not exist	do not exist
Type-Ⅱ	$ 2(2n) \times 2(2n) $	do not exist	do not exist
Type-Ⅱ	$ 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]	Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[2]	Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[3]	Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2559-2599. doi: 10.3934/dcds.2020375
[4]	Thomas Alazard. A minicourse on the low Mach number limit. Discrete & Continuous Dynamical Systems - S, 2008, 1 (3) : 365-404. doi: 10.3934/dcdss.2008.1.365
[5]	Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25
[6]	Lars Grüne, Luca Mechelli, Simon Pirkelmann, Stefan Volkwein. Performance estimates for economic model predictive control and their application in proper orthogonal decomposition-based implementations. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021013
[7]	Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141
[8]	Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3651-3682. doi: 10.3934/dcds.2021011
[9]	Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109
[10]	Guangying Lv, Jinlong Wei, Guang-an Zou. Noise and stability in reaction-diffusion equations. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021005
[11]	Hai-Liang Li, Tong Yang, Mingying Zhong. Diffusion limit of the Vlasov-Poisson-Boltzmann system. Kinetic & Related Models, 2021, 14 (2) : 211-255. doi: 10.3934/krm.2021003
[12]	Maxime Breden, Christian Kuehn, Cinzia Soresina. On the influence of cross-diffusion in pattern formation. Journal of Computational Dynamics, 2021 doi: 10.3934/jcd.2021010
[13]	Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[14]	Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189
[15]	Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258
[16]	Yizhuo Wang, Shangjiang Guo. A SIS reaction-diffusion model with a free boundary condition and nonhomogeneous coefficients. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1627-1652. doi: 10.3934/dcdsb.2018223
[17]	Dan Wei, Shangjiang Guo. Qualitative analysis of a Lotka-Volterra competition-diffusion-advection system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2599-2623. doi: 10.3934/dcdsb.2020197
[18]	Mohamed Ouzahra. Approximate controllability of the semilinear reaction-diffusion equation governed by a multiplicative control. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021081
[19]	Ágota P. Horváth. Discrete diffusion semigroups associated with Jacobi-Dunkl and exceptional Jacobi polynomials. Communications on Pure & Applied Analysis, 2021, 20 (3) : 975-994. doi: 10.3934/cpaa.2021002
[20]	Meng-Xue Chang, Bang-Sheng Han, Xiao-Ming Fan. Global dynamics of the solution for a bistable reaction diffusion equation with nonlocal effect. Electronic Research Archive, , () : -. doi: 10.3934/era.2021024

2019 Impact Factor: 0.734

Tools

Metrics

Tools

Article outline

Figures and Tables

2019 Impact Factor: 0.734

Tools

Figures and Tables

2019 Impact Factor: 0.734

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors