• 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. GuptaS. K. PandeyI. 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. KranzG. LeanderK. 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. LiS. SunC. LiZ. 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. SajadiehM. DakhilalianH. 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. GuptaS. K. PandeyI. 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. KranzG. LeanderK. 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. LiS. SunC. LiZ. 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. SajadiehM. DakhilalianH. 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]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. Aims: Average information matrix splitting. Mathematical Foundations of Computing, 2020  doi: 10.3934/mfc.2020012

[17]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020012

[18]

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

[19]

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

[20]

Yitong Guo, Bingo Wing-Kuen Ling. Principal component analysis with drop rank covariance matrix. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020072

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (41)
  • HTML views (179)
  • Cited by (0)

Other articles
by authors

[Back to Top]