American Institute of Mathematical Sciences

Advanced
November  2021, 15(4): 589-610. doi: 10.3934/amc.2020084

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

Mohsen Mousavi 1, , Ali Zaghian 1, and  Morteza Esmaeili 2,3,,

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

Received  June 2019 Revised  March 2020 Published  November 2021 Early access  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.

Keywords: Cauchy matrix, MDS matrix, lightweight MDS matrix, diffusion layer, multiple MDS matrices.
Mathematics Subject Classification: Primary: 94A60, 11T71; Secondary: 14G50.
Citation: Mohsen Mousavi, Ali Zaghian, Morteza Esmaeili. Involutory-Multiple-Lightweight MDS Matrices based on Cauchy-type Matrices. Advances in Mathematics of Communications, 2021, 15 (4) : 589-610. 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]

Shi Wang, Yongqiang Li, Shizhu Tian, Xiangyong Zeng. Four by four MDS matrices with the fewest XOR gates based on words. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021025
[2]

Janne I. Kokkala, Patric R. J.  Östergård. Further results on the classification of MDS codes. Advances in Mathematics of Communications, 2016, 10 (3) : 489-498. doi: 10.3934/amc.2016020
[3]

Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco. On the weight distribution of the cosets of MDS codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021042
[4]

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
[5]

Can Xiang, Jinquan Luo. Some subfield codes from MDS codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021023
[6]

Simeon Ball, Guillermo Gamboa, Michel Lavrauw. On additive MDS codes over small fields. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021024
[7]

Ilias S. Kotsireas, Christos Koukouvinos, Dimitris E. Simos. MDS and near-MDS self-dual codes over large prime fields. Advances in Mathematics of Communications, 2009, 3 (4) : 349-361. doi: 10.3934/amc.2009.3.349
[8]

Eric Bedford, Kyounghee Kim. Degree growth of matrix inversion: Birational maps of symmetric, cyclic matrices. Discrete & Continuous Dynamical Systems, 2008, 21 (4) : 977-1013. doi: 10.3934/dcds.2008.21.977
[9]

Anna-Lena Horlemann-Trautmann, Alessandro Neri. A complete classification of partial MDS (maximally recoverable) codes with one global parity. Advances in Mathematics of Communications, 2020, 14 (1) : 69-88. doi: 10.3934/amc.2020006
[10]

Sara D. Cardell, Joan-Josep Climent, Daniel Panario, Brett Stevens. A construction of $ \mathbb{F}_2 $-linear cyclic, MDS codes. Advances in Mathematics of Communications, 2020, 14 (3) : 437-453. doi: 10.3934/amc.2020047
[11]

Diego Napp, Roxana Smarandache. Constructing strongly-MDS convolutional codes with maximum distance profile. Advances in Mathematics of Communications, 2016, 10 (2) : 275-290. doi: 10.3934/amc.2016005
[12]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149
[13]

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
[14]

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

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
[16]

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

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

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

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

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

2020 Impact Factor: 0.935

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences