On Lightweight 4x4 MDS Matrices over Binary Field Extensions

Year 2020, Volume: 9 Issue: 2, 94 - 103, 01.06.2020

Fatma Buyuksaracoglu Sakalli Ozlem Aydin Gokhan Tuncay Meltem Kurt Pehlivanoglu Gulsum Gozde Guzel Muharrem Tolga Sakalli

Abstract

Maximum Distance Separable MDS matrices are used as the main part of diffusion layers in block ciphers and hash functions. MDS matrices derived from MDS codes have the maximum differential and linear branch number, which provide resistance against some well-known attacks like differential and linear cryptanalysis together with the use of a nonlinear layer e.g. S-boxes in a round function of a block cipher. In this paper, we introduce generic methods to generate lightweight $k \times k$ involutory/non-involutory MDS matrices over $\F_{2^m}$ and present the lightest involutory/non-involutory $4 \times 4$ MDS matrices over $\F_{2^4}$ to the best of our knowledge by considering XOR count metric, which is defined to estimate hardware implementation cost. Also, the results are obtained by using a global optimization technique, namely Boyar-Peralta algorithm.

Keywords

MDS matrices, diffusion layer, symmetric key cryptography

References

• C.E. Shannon.“Communication Theory of Secrecy Systems”, Bell System Technical Journal, Vol.28, pp. 656-715, October 1949.
• E. Biham, A. Shamir. “Differential cryptanalysis of DES-like cryptosystems”, CRYPTO’90, Santa Barbara, CA, USA, LNCS, Vol.537, pp. 2-21, 11-15 August 1990.
• M. Matsui. “Linear cryptanalysis method for DES cipher”, EU- ROCRYPT’93, Lofthus, Norway, LNCS, Vol.765, pp. 386-397, 23-27 May 1993.
• A.M. Youssef, S. Mister, S.E. Tavares. “On the Design of Linear Transformation for Substitution Permutation Encryption Net- works”, Selected Areas in Cryptography (SAC), Ottawa Ontario, Canada, pp. 40-48, 11-12 August 1997.
• J. Guo, T. Peyrin, A. Poschmann. “The PHOTON family of lightweight hash functions”, CRYPTO 2011, Santa Barbara, CA, USA, LNCS, Vol.6841, pp. 222-239, 14-18 August 2011.
• K.C. Gupta, I.G. Ray. “On constructions of MDS matrices from companion matrices for lightweight cryptography”, CD-ARES 2013, Regensburg, Germany, LNCS, Vol.8128, pp. 29-43, 2-6 September 2013.
• J. Lacan, J. Fimes. “Systematic MDS erasure codes based on vandermonde matrices”, IEEE Communications Letters, Vol.8, No.9, pp. 570-572, September 2004.
• M. Sajadieh, M. Dakhilalian, H. Mala, B. Omoomi. “On con- struction of involutory MDS matrices from Vandermonde Matri- ces in GF (2q)”, Design, Codes and Cryptography, Vol.64, No.3, pp.287-308, September 2012. [9] G.G. G¨uzel, M.T. Sakallı, S. C¸ engellenmis¸. “A New Matrix Form to Generate All 3 × 3 Involutory MDS Matrices over Fm”, Information Processing Letters, Vol.147, pp. 61-68, March 2019. V. Rijmen, Y.
• M. Sajadieh, M. Dakhilalian, H. Mala, P. Sepehrdad. “Recursive Diffusion Layers for Block Ciphers and Hash Functions”, FSE 2012, Washington DC, USA, LNCS, Vol.7549, pp. 385-401, 19- 21 March 2012.
• S. Wu, M. Wang, W. Wu. “Recursive Diffusion Layers for (Lightweight) Block Ciphers and Hash Functions”, Selected Areas in Cryptography (SAC), Windsor, ON, Canada, LNCS, Vol.7707, pp. 355-371, 15-16 August 2012.
• S.M. Sim, K. Khoo, F. Oggier, T. Peyrin. “Lightweight MDS In- volution Matrices”, FSE 2015, Istanbul, Turkey, LNCS, Vol.9054, pp. 471-493, 8-11 March 2015.
• S. Akleylek, M.T. Sakallı. “Some Results on MDS Matrices”, 9th International Conference on Information Security and Cryp- tology (ISCTURKEY 2016), Ankara, Turkey, pp. 35-38, 25-26 October 2016.
• M.K. Pehlivano˘glu, M.T. Sakallı, S. Akleylek, N. Duru, V. Rij- men. “Generalisation of Hadamard Matrix to Generate Involutory MDS Matrices for Lightweight Cryptography”, IET Information Security, Vol.12, No.4, pp. 348-355, July 2018.
• M.T. Sakallı, S. Akleylek, K. Akkanat, V. Rijmen. “On the automorphisms and isomorphisms of MDS matrices and their efficient implementations”, Turkish Journal of Electrical & Com- puter Sciences, Vol.28, No. 1, pp. 275-287, January 2020.
• K. Khoo, T. Peyrin, A.Y. Poschmann, and H. Yap. “FOAM: Searching for Hardware-Optimal SPN Structures and Compo- nents with a Fair Comparison”, CHES 2014, Busan, South Korea, LNCS, Vol.8731, pp. 433-450, 23-26 September 2014.
• T. Kranz, G. Leander, K. Stoffelen, and F. Wiemer. “Shorter linear straight-line programs for MDS matrices”, IACR Trans- actions on Symmetric Cryptology, Vol.2017, No.4, pp. 188-211, December 2017.
• J. Boyar, R. Peralta. “A new combinational logic minimization technique with applications to cryptology”, SEA 2010, Naples, Italy, LNCS, vol. 6049, pp. 178–189, 20-22 May 2010.
• F.J. MacWilliams, N.J.A. Sloane. The theory of error-correcting codes. North-Holland, Amsterdam:North Holland Publishing Co., 1977.
• J. Jean, T. Peyrin, S.M. Sim, J. Tourteaux. “Optimizing imple- mentations of lightweight building blocks”, IACR Transactions on Symmetric Cryptology, Vol.2017, No.4, pp. 130-168, Decem- ber 2017.
• C. Beierle, T. Kranz, G. Leander. “Lightweight multiplication in GF (2n) with applications to MDS matrices”, CRYPTO 2016, Santa Barbara, USA, LNCS, vol. 9814, pp. 625-653, 14-18 August 2016.
• S. Sarkar, H. Syed. “Lighweight diffusion layer: importance of Toeplitz matrices”, IACR Transactions on Symmetric Cryptology, Vol.2016, No.1, pp. 95-113, January 2016.
• M. Liu, S.M. Sim. “Lightweight MDS generalized circulant matrices”, FSE 2016, Bochum, Germany, LNCS, Vol. 9783, pp. 101–120, 20-23 March 2016.
• Y. Li, M. Wang. “On the construction of lightweight circulant involutory MDS matrices”, FSE 2016, Bochum, Germany, LNCS, Vol. 9783, pp. 121–139, 20-23 March 2016.