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

Mohsen Mousavi; Ali Zaghian; Morteza Esmaeili

doi:10.3934/amc.2020084

Article Contents

2021, Volume 15, Issue 4: 589-610. Doi: 10.3934/amc.2020084

This issue Previous Article Rank weights for arbitrary finite field extensions Next Article An overview on skew constacyclic codes and their subclass of LCD codes

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
^* Corresponding author: Morteza Esmaeili

Received: May 31, 2019

Revised: February 29, 2020

Early access: June 2020

Published: November 2021

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 94A60, 11T71; Secondary: 14G50.

Citation:

Full Text(HTML)

Related Papers

Cited by

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.
[2]	P. Barreto and V. Rijmen, The Khazad legacy-level block cipher, in Proceedings of the First Open NESSIE Workshop, Belgium, (2000).
[3]	P. Barreto and V. Rijmen, The Anubis block cipher, in Proceedings of the First Open NESSIE Workshop, Belgium, (2000).
[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.
[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.
[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.
[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).
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[21]	I. G. Macdonald, Symmetric Functions and Hall Polynomials, 2^nd edition, The Clarendon Press, Oxford University Press, New York, 1995.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[31]	J. R. Stembridge, A concise proof of the Littlewood-Richardson rule, Electron. J. Combin., 9 (2002), 1-4. doi: 10.37236/1666.
[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.