# American Institute of Mathematical Sciences

• Previous Article
New optimal error-correcting codes for crosstalk avoidance in on-chip data buses
• AMC Home
• This Issue
• Next Article
On the equivalence of several classes of quaternary sequences with optimal autocorrelation and length $2p$
doi: 10.3934/amc.2020084

## Involutory-Multiple-Lightweight MDS Matrices based on Cauchy-type Matrices

 1 Department of Applied Mathematics, Malek Ashtar University of Technology, Isfahan, Iran 2 Department of Mathematical Sciences, Isfahan University of Technology, Isfahan, Iran 3 Department of Electrical & Computer Engineering, University of Victoria, Victoria, BC, Canada

* Corresponding author: Morteza Esmaeili

Revised  March 2020 Published  June 2020

One of the best methods for constructing maximum distance separable ($\operatorname{MDS}$) matrices is based on making use of Cauchy matrices. In this paper, by using some extensions of Cauchy matrices, we introduce several new forms of $\operatorname{MDS}$ matrices over finite fields of characteristic 2. A known extension of a Cauchy matrix, called the Cauchy-like matrix, with application in coding theory was introduced in 1985. One of the main contributions of this paper is to apply Cauchy-like matrices to introduce $2n \times 2n$ involutory $\operatorname{MDS}$ matrices in the semi-Hadamard form which is a generalization of the previously known methods. We make use of Cauchy-like matrices to construct multiple $\operatorname{MDS}$ matrices which can be used in the Feistel structures. We also introduce a new extension of Cauchy matrices to be referred to as Cauchy-light matrices. The introduced Cauchy-light matrices are applied to construct $n \times n$ $\operatorname{MDS}$ matrices having at least $3n-3$ entries equal to the unit element $1$; such a matrix is called a lightweight $\operatorname{MDS}$ matrix and can be used in the lightweight cryptography. A simple closed-form expression is given for the determinant of Cauchy-light matrices.

Citation: Mohsen Mousavi, Ali Zaghian, Morteza Esmaeili. Involutory-Multiple-Lightweight MDS Matrices based on Cauchy-type Matrices. Advances in Mathematics of Communications, doi: 10.3934/amc.2020084
##### References:
 [1] D. Augot and M. Finiasz, Direct construction of recursive MDS diffusion layers using shortened BCH codes, in Fast Software Encryption. FSE 2014, Vol. 8540, Springer, Berlin, Heidelberg, 2014, 3-17. doi: 10.1007/978-3-662-46706-0_1.  Google Scholar [2] P. Barreto and V. Rijmen, The Khazad legacy-level block cipher, in Proceedings of the First Open NESSIE Workshop, Belgium, (2000). Google Scholar [3] P. Barreto and V. Rijmen, The Anubis block cipher, in Proceedings of the First Open NESSIE Workshop, Belgium, (2000). Google Scholar [4] C. Beierle, T. Kranz and G. Leander, Lightweight multiplication in $GF(2^n)$ with applications to MDS matrices, in Advances in Cryptology. CRYPTO 2016. Part 1, Lecture Notes in Comput. Sci., Vol. 9814, Springer, Berlin, 2016,625-653. doi: 10.1007/978-3-662-53018-4_23.  Google Scholar [5] T. P. Berger, G. Paul and S. Vaudenay, eds., Construction of recursive MDS diffusion layers from gabidulin codes, in Progress in Cryptology. INDOCRYPT 2013, Vol. 8250, Springer, Cham, 2013,274-285. doi: 10.1007/978-3-319-03515-4.  Google Scholar [6] J. Daemen and V. Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-662-04722-4.  Google Scholar [7] G. Filho, P. Barreto and V. Rijmen, The Maelstrom-$0$ hash function, in Proceedings of the Sixth Brazilian Symposium on Information and Computer Systems Security, (2006). Google Scholar [8] J. Guo, T. Peyrin and A. Poschmann, The PHOTON family of lightweight hash functions, in Advances in Cryptology. CRYPTO 2011, Vol. 6841, Springer, Heidelberg, 2011,222-239. doi: 10.1007/978-3-642-22792-9.  Google Scholar [9] K. C. Gupta and I. G. Ray, On constructions of MDS matrices from companion matrices for lightweight cryptography, in Security Engineering and Intelligence Informatics. CD-ARES 2013, Vol. 8128, Springer, Berlin, Heidelberg, 2013, 29-43. doi: 10.1007/978-3-642-40588-4_3.  Google Scholar [10] K. C. Gupta and I. G. Ray, On constructions of involutory MDS matrices, in Progress in Cryptology. AFRICACRYPT 2013, Vol. 7918, Springer, Heidelberg, 2013, 43-60. doi: 10.1007/978-3-642-38553-7_3.  Google Scholar [11] K. C. Gupta and I. G. Ray, Cryptographically significant MDS matrices based on circulant and circulant-like matrices for lightweight applications, Cryptogr. Commun., 7 (2015), 257-287.  doi: 10.1007/s12095-014-0116-3.  Google Scholar [12] K. C. Gupta, S. K. Pandey, I. G. Ray and S. Samanta, Cryptographically significant MDS matrices over finite fields: A brief survey and some generalized results, Adv. Math. Commun., 13 (2019), 779-843.  doi: 10.3934/amc.2019045.  Google Scholar [13] H. Hou and S. Y. Han, A new construction and an efficient decoding method for Rabin-like codes, IEEE Transactions on Communications, 66 (2018), 521-533.  doi: 10.1109/TCOMM.2017.2766140.  Google Scholar [14] P. Junod and S. Vaudenay, Perfect diffusion primitives for block ciphers building efficient MDS matrices, in Selected Areas in Cryptography. SAC 2004, Vol. 3357, Springer, Berlin, 2005, 84-99. doi: 10.1007/978-3-540-30564-4_6.  Google Scholar [15] K. Khoo, T. Peyrin, A. Y. Poschmann and H. Yap, FOAM: Searching for hardware-optimal SPN structures and components with a fair comparison, in Cryptographic Hardware and Embedded Systems. CHES 2014, Vol. 8731, Springer, Berlin, Heidelberg, 2014,433-450. doi: 10.1007/978-3-662-44709-3_24.  Google Scholar [16] L. Kölsch, XOR-counts and lightweight multiplication with fixed elements in binary finite fields, in Advances in Cryptology. EUROCRYPT 2019, Vol. 11476, Springer, Cham, 2019,285-312. doi: 10.1007/978-3-030-17653-2_10.  Google Scholar [17] H. Kranz, G. Leander, K. Stoffelen and F. Wiemer, Shorter linear straight-line programs for MDS matrices, IACR Transactions on Symmetric Cryptology, 2017 (2017), 188-211.   Google Scholar [18] J. Lacan and J. Fimes, Systematic MDS erasure codes based on Vandermonde matrices, IEEE Communications Letters, 8 (2004), 570-572.  doi: 10.1109/LCOMM.2004.833807.  Google Scholar [19] S. Li, S. Sun, C. Li, Z. Wei and L. Hu, Constructing low-latency involutory MDS matrices with lightweight circuits, IACR Transactions on Symmetric Cryptology, 2019 (2019), 84-117.   Google Scholar [20] M. Liu and S. M. Sim, Lightweight MDS generalized circulant matrices, in Fast Software Encryption. FSE 2016, Vol. 9783, Springer, Berlin, Heidelberg, 2016,101-120. doi: 10.1007/978-3-662-52993-5_6.  Google Scholar [21] I. G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edition, The Clarendon Press, Oxford University Press, New York, 1995.  Google Scholar [22] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes II, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar [23] C. Paar, Optimized arithmetic for Reed-Solomon encoders, in Proceedings of IEEE International Symposium on Information Theory, Ulm, Germany, (1997), 250-250. doi: 10.1109/ISIT.1997.613165.  Google Scholar [24] R. M. Roth and G. Seroussi, On generator matrices of MDS codes, IEEE Trans. Inform. Theory, 31 (1985), 826-830.  doi: 10.1109/TIT.1985.1057113.  Google Scholar [25] R. M. Roth and A. Lempel, On MDS codes via Cauchy matrices, IEEE Trans. Inform. Theory, 35 (1989), 1314-1319.  doi: 10.1109/18.45291.  Google Scholar [26] M. Sajadieh, M. Dakhilalian, H. Mala and B. Omoomi, On construction of involutory MDS matrices from Vandermonde Matrices in GF($2^q$), Des. Codes Cryptogr., 64 (2012), 287-308.  doi: 10.1007/s10623-011-9578-x.  Google Scholar [27] C. Schindelhauer and C. Ortolf, Maximum distance separable codes based on circulant Cauchy matrices, in Structural Information and Communication Complexity. SIROCCO 2013, Vol. 8179, Springer, Cham, 2013,334-345. doi: 10.1007/978-3-319-03578-9_28.  Google Scholar [28] C. E. Shannon, Communication theory of secrecy systems, Bell System Tech. J., 28 (1949), 656-715.  doi: 10.1002/j.1538-7305.1949.tb00928.x.  Google Scholar [29] T. Shirai and K. Shibutani, Improving immunity of feistel ciphers against differential cryptanalysis by using multiple MDS matrices, in Fast Software Encryption. FSE 2004, Vol. 3017, Springer, Berlin, Heidelberg, 2004,260-278. doi: 10.1007/978-3-540-25937-4_17.  Google Scholar [30] S. M. Sim, K. Khoo, F. Oggier and T. Peyrin, Lightweight MDS involution matrices, in Fast Software Encryption. FSE 2015, Vol. 9054, Springer, Berlin, Heidelberg, 2015,471-493. doi: 10.1007/978-3-662-48116-5_23.  Google Scholar [31] J. R. Stembridge, A concise proof of the Littlewood-Richardson rule, Electron. J. Combin., 9 (2002), 1-4.  doi: 10.37236/1666.  Google Scholar [32] S. Wu, M. Wang and W. Wu, Recursive diffusion layers for (lightweight) block ciphers and hash functions, in Selected Areas in Cryptography. SAC 2012, Vol. 7707, Springer, Heidelberg, 2012,355-371. doi: 10.1007/978-3-642-35999-6.  Google Scholar

show all references

##### References:
 [1] D. Augot and M. Finiasz, Direct construction of recursive MDS diffusion layers using shortened BCH codes, in Fast Software Encryption. FSE 2014, Vol. 8540, Springer, Berlin, Heidelberg, 2014, 3-17. doi: 10.1007/978-3-662-46706-0_1.  Google Scholar [2] P. Barreto and V. Rijmen, The Khazad legacy-level block cipher, in Proceedings of the First Open NESSIE Workshop, Belgium, (2000). Google Scholar [3] P. Barreto and V. Rijmen, The Anubis block cipher, in Proceedings of the First Open NESSIE Workshop, Belgium, (2000). Google Scholar [4] C. Beierle, T. Kranz and G. Leander, Lightweight multiplication in $GF(2^n)$ with applications to MDS matrices, in Advances in Cryptology. CRYPTO 2016. Part 1, Lecture Notes in Comput. Sci., Vol. 9814, Springer, Berlin, 2016,625-653. doi: 10.1007/978-3-662-53018-4_23.  Google Scholar [5] T. P. Berger, G. Paul and S. Vaudenay, eds., Construction of recursive MDS diffusion layers from gabidulin codes, in Progress in Cryptology. INDOCRYPT 2013, Vol. 8250, Springer, Cham, 2013,274-285. doi: 10.1007/978-3-319-03515-4.  Google Scholar [6] J. Daemen and V. Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-662-04722-4.  Google Scholar [7] G. Filho, P. Barreto and V. Rijmen, The Maelstrom-$0$ hash function, in Proceedings of the Sixth Brazilian Symposium on Information and Computer Systems Security, (2006). Google Scholar [8] J. Guo, T. Peyrin and A. Poschmann, The PHOTON family of lightweight hash functions, in Advances in Cryptology. CRYPTO 2011, Vol. 6841, Springer, Heidelberg, 2011,222-239. doi: 10.1007/978-3-642-22792-9.  Google Scholar [9] K. C. Gupta and I. G. Ray, On constructions of MDS matrices from companion matrices for lightweight cryptography, in Security Engineering and Intelligence Informatics. CD-ARES 2013, Vol. 8128, Springer, Berlin, Heidelberg, 2013, 29-43. doi: 10.1007/978-3-642-40588-4_3.  Google Scholar [10] K. C. Gupta and I. G. Ray, On constructions of involutory MDS matrices, in Progress in Cryptology. AFRICACRYPT 2013, Vol. 7918, Springer, Heidelberg, 2013, 43-60. doi: 10.1007/978-3-642-38553-7_3.  Google Scholar [11] K. C. Gupta and I. G. Ray, Cryptographically significant MDS matrices based on circulant and circulant-like matrices for lightweight applications, Cryptogr. Commun., 7 (2015), 257-287.  doi: 10.1007/s12095-014-0116-3.  Google Scholar [12] K. C. Gupta, S. K. Pandey, I. G. Ray and S. Samanta, Cryptographically significant MDS matrices over finite fields: A brief survey and some generalized results, Adv. Math. Commun., 13 (2019), 779-843.  doi: 10.3934/amc.2019045.  Google Scholar [13] H. Hou and S. Y. Han, A new construction and an efficient decoding method for Rabin-like codes, IEEE Transactions on Communications, 66 (2018), 521-533.  doi: 10.1109/TCOMM.2017.2766140.  Google Scholar [14] P. Junod and S. Vaudenay, Perfect diffusion primitives for block ciphers building efficient MDS matrices, in Selected Areas in Cryptography. SAC 2004, Vol. 3357, Springer, Berlin, 2005, 84-99. doi: 10.1007/978-3-540-30564-4_6.  Google Scholar [15] K. Khoo, T. Peyrin, A. Y. Poschmann and H. Yap, FOAM: Searching for hardware-optimal SPN structures and components with a fair comparison, in Cryptographic Hardware and Embedded Systems. CHES 2014, Vol. 8731, Springer, Berlin, Heidelberg, 2014,433-450. doi: 10.1007/978-3-662-44709-3_24.  Google Scholar [16] L. Kölsch, XOR-counts and lightweight multiplication with fixed elements in binary finite fields, in Advances in Cryptology. EUROCRYPT 2019, Vol. 11476, Springer, Cham, 2019,285-312. doi: 10.1007/978-3-030-17653-2_10.  Google Scholar [17] H. Kranz, G. Leander, K. Stoffelen and F. Wiemer, Shorter linear straight-line programs for MDS matrices, IACR Transactions on Symmetric Cryptology, 2017 (2017), 188-211.   Google Scholar [18] J. Lacan and J. Fimes, Systematic MDS erasure codes based on Vandermonde matrices, IEEE Communications Letters, 8 (2004), 570-572.  doi: 10.1109/LCOMM.2004.833807.  Google Scholar [19] S. Li, S. Sun, C. Li, Z. Wei and L. Hu, Constructing low-latency involutory MDS matrices with lightweight circuits, IACR Transactions on Symmetric Cryptology, 2019 (2019), 84-117.   Google Scholar [20] M. Liu and S. M. Sim, Lightweight MDS generalized circulant matrices, in Fast Software Encryption. FSE 2016, Vol. 9783, Springer, Berlin, Heidelberg, 2016,101-120. doi: 10.1007/978-3-662-52993-5_6.  Google Scholar [21] I. G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edition, The Clarendon Press, Oxford University Press, New York, 1995.  Google Scholar [22] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes II, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar [23] C. Paar, Optimized arithmetic for Reed-Solomon encoders, in Proceedings of IEEE International Symposium on Information Theory, Ulm, Germany, (1997), 250-250. doi: 10.1109/ISIT.1997.613165.  Google Scholar [24] R. M. Roth and G. Seroussi, On generator matrices of MDS codes, IEEE Trans. Inform. Theory, 31 (1985), 826-830.  doi: 10.1109/TIT.1985.1057113.  Google Scholar [25] R. M. Roth and A. Lempel, On MDS codes via Cauchy matrices, IEEE Trans. Inform. Theory, 35 (1989), 1314-1319.  doi: 10.1109/18.45291.  Google Scholar [26] M. Sajadieh, M. Dakhilalian, H. Mala and B. Omoomi, On construction of involutory MDS matrices from Vandermonde Matrices in GF($2^q$), Des. Codes Cryptogr., 64 (2012), 287-308.  doi: 10.1007/s10623-011-9578-x.  Google Scholar [27] C. Schindelhauer and C. Ortolf, Maximum distance separable codes based on circulant Cauchy matrices, in Structural Information and Communication Complexity. SIROCCO 2013, Vol. 8179, Springer, Cham, 2013,334-345. doi: 10.1007/978-3-319-03578-9_28.  Google Scholar [28] C. E. Shannon, Communication theory of secrecy systems, Bell System Tech. J., 28 (1949), 656-715.  doi: 10.1002/j.1538-7305.1949.tb00928.x.  Google Scholar [29] T. Shirai and K. Shibutani, Improving immunity of feistel ciphers against differential cryptanalysis by using multiple MDS matrices, in Fast Software Encryption. FSE 2004, Vol. 3017, Springer, Berlin, Heidelberg, 2004,260-278. doi: 10.1007/978-3-540-25937-4_17.  Google Scholar [30] S. M. Sim, K. Khoo, F. Oggier and T. Peyrin, Lightweight MDS involution matrices, in Fast Software Encryption. FSE 2015, Vol. 9054, Springer, Berlin, Heidelberg, 2015,471-493. doi: 10.1007/978-3-662-48116-5_23.  Google Scholar [31] J. R. Stembridge, A concise proof of the Littlewood-Richardson rule, Electron. J. Combin., 9 (2002), 1-4.  doi: 10.37236/1666.  Google Scholar [32] S. Wu, M. Wang and W. Wu, Recursive diffusion layers for (lightweight) block ciphers and hash functions, in Selected Areas in Cryptography. SAC 2012, Vol. 7707, Springer, Heidelberg, 2012,355-371. doi: 10.1007/978-3-642-35999-6.  Google Scholar
 [1] Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012 [2] 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 [3] S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435 [4] Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018 [5] 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 - A, 2020  doi: 10.3934/dcds.2020375 [6] Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076 [7] Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016 [8] Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272 [9] Zhilei Liang, Jiangyu Shuai. Existence of strong solution for the Cauchy problem of fully compressible Navier-Stokes equations in two dimensions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020348 [10] Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044 [11] Meilan Cai, Maoan Han. Limit cycle bifurcations in a class of piecewise smooth cubic systems with multiple parameters. Communications on Pure & Applied Analysis, 2021, 20 (1) : 55-75. doi: 10.3934/cpaa.2020257 [12] Stefan Ruschel, Serhiy Yanchuk. The Spectrum of delay differential equations with multiple hierarchical large delays. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 151-175. doi: 10.3934/dcdss.2020321 [13] Weiwei Liu, Jinliang Wang, Yuming Chen. Threshold dynamics of a delayed nonlocal reaction-diffusion cholera model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020316 [14] Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321 [15] Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458 [16] Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319 [17] H. M. Srivastava, H. I. Abdel-Gawad, Khaled Mohammed Saad. Oscillatory states and patterns formation in a two-cell cubic autocatalytic reaction-diffusion model subjected to the Dirichlet conditions. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020433 [18] Lin Shi, Xuemin Wang, Dingshi Li. Limiting behavior of non-autonomous stochastic reaction-diffusion equations with colored noise on unbounded thin domains. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5367-5386. doi: 10.3934/cpaa.2020242 [19] Hai-Feng Huo, Shi-Ke Hu, Hong Xiang. Traveling wave solution for a diffusion SEIR epidemic model with self-protection and treatment. Electronic Research Archive, , () : -. doi: 10.3934/era.2020118 [20] Karoline Disser. Global existence and uniqueness for a volume-surface reaction-nonlinear-diffusion system. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 321-330. doi: 10.3934/dcdss.2020326

2019 Impact Factor: 0.734

## Tools

Article outline

Figures and Tables