Lightweight 4x4 MDS Matrices for Hardware-Oriented Cryptographic Primitives



1 Shahid Rajaee Teacher Training University

2 Shahid Beheshti University

3 Department of Mathematical and Computer Sciences, Kharazmi University

4 Malek Ashtar University of Technology



Linear diffusion layer is an important part of lightweight block ciphers and hash functions. This paper presents an efficient class of lightweight 4x4 MDS matrices such that the implementation cost of them and their corresponding inverses are equal. The main target of the paper is hardware oriented cryptographic primitives and the implementation cost is measured in terms of the required number of XORs. Firstly, we mathematically characterize the MDS property of a class of matrices (derived from the product of binary matrices and companion matrices of $\sigma$-LFSRs aka recursive diffusion layers) whose implementation cost is $10m+4$ XORs for 4 <= m <= 8, where $m$ is the bit length of inputs. Then, based on the mathematical investigation, we further extend the search space and propose new families of 4x 4 MDS matrices with 8m+4 and 8m+3 XOR implementation cost. The lightest MDS matrices by our new approach have the same implementation cost as the lightest existent matrix.


[1] Jian Guo, Thomas Peyrin, and Axel Poschmann. The PHOTON family of lightweight hash functions. In Phillip Rogaway, editor, Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, volume 6841 of Lecture Notes in Computer Science, pages 222– 239. Springer, 2011.

[2] Mahdi Sajadieh, Mohammad Dakhilalian, Hamid Mala, and Pouyan Sepehrdad. Efficient recursive diffusion layers for block ciphers and hash functions. J. Cryptology, 28(2):240–256, 2015.

[3] Shengbao Wu, Mingsheng Wang, and Wenling Wu. Recursive diffusion layers for (lightweight) block ciphers and hash functions. In Selected Areas in Cryptography, 19th International Conference, SAC 2012, Windsor, ON, Canada, August 15-16, 2012, Revised Selected Papers, pages 355–371, 2012.

[4] Guang Zeng, Wenbao Han, and Kaicheng He. High efficiency feedback shift register: sigma-lfsr. IACR Trans. Symmetric Cryptol., 2007:114, 2007.

[5] Hong Xu, Yonghui Zheng, and Xuejia Lai. Construction of perfect diffusion layers from linear feedback shift registers. IET Information Security, 9(2):127–135, 2015.

[6] Christof Beierle, Thorsten Kranz, and Gregor Leander. Lightweight multiplication in GF(2ˆn) with applications to MDS matrices. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, volume 9814 of Lecture Notes in Computer Science, pages 625–653. Springer, 2016.

[7] Yongqiang Li and Mingsheng Wang. On the construction of lightweight circulant involutory MDS matrices. In Fast Software Encryption - 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers, pages 121–139, 2016.

[8] Jian Bai and Dingkang Wang. The lightest 4x4 MDS matrices over GL(4, F2). IACR Trans. Symmetric Cryptol., 2016:686, 2016.

[9] Sumanta Sarkar and Habeeb Syed. Lightweight diffusion layer: Importance of toeplitz matrices. IACR Trans. Symmetric Cryptol., 2016(1):95– 113, 2016.

[10] Zhiyuan Guo, Renzhang Liu, Si Gao, Wenling Wu, and Dongdai Lin. Direct construction of optimal rotational-xor diffusion primitives. IACR Trans. Symmetric Cryptol., 2017(4):169–187, 2017.

[11] Victor Cauchois, Pierre Loidreau, and Nabil Merkiche. Direct construction of quasi-involutory recursive-like MDS matrices from 2-cyclic codes. IACR Trans. Symmetric Cryptol., 2016(2):80–98, 2016.

[12] Shiyi Zhang, Yongjuan Wang, Yang Gao, and Tao Wang. On the construction of the 4 x 4 lightest circulant MDS matrices. In Proceedings of the 2017 International Conference on Cryptography, Security and Privacy, ICCSP 2017, Wuhan, China, March 17 - 19, 2017, pages 1–6, 2017.

[13] Lijing Zhou, Licheng Wang, and Yiru Sun. On efficient constructions of lightweight MDS matrices. IACR Trans. Symmetric Cryptol., 2018(1):180– 200, 2018.

[14] Thorsten Kranz, Gregor Leander, Ko Stoffelen, and Friedrich Wiemer. Shorter linear straightline programs for MDS matrices. IACR Trans. Symmetric Cryptol., 2017(4):188–211, 2017.

[15] Dylan Toh, Jacob Teo, Khoongming Khoo, and Siang Meng Sim. Lightweight MDS serial-type matrices with minimal fixed XOR count. In Progress in Cryptology - AFRICACRYPT 2018 - 10th International Conference on Cryptology in Africa, Marrakesh, Morocco, May 7-9, 2018, Proceedings, pages 51–71, 2018.

[16] S´ebastien Duval and Ga¨etan Leurent. MDS matrices with lightweight circuits. IACR Trans. Symmetric Cryptol., 2018(2):48–78, 2018.

[17] Ruoxin Zhao, Baofeng Wu, Rui Zhang, and Qian Zhang. Designing optimal implementations of linear layers (full version). Cryptology ePrint Archive, Report 2016/1118, 2016.

[18] Joan Daemen and Vincent Rijmen. The Design of Rijndael: AES - The Advanced Encryption Standard. Information Security and Cryptography. Springer, 2002.

[19] S. Ling and C. Xing. Coding Theory: A First Course. Cambridge University Press, 2004.

[20] Mario Blaum and Ron M. Roth. On lowest density MDS codes. IEEE Trans. Information Theory, 45(1):46–59, 1999. [21] Daniel S. Silver Ivan Kovacs and Susan G. Williams. Determinants of commuting-block matrices. The American Mathematical Monthly, 106(10):950–952, 1999.