On the Construction of Lightweight Circulant Maximum Distance Separable Matrices

Authors: Qinyi Mei, Li-Ping Wang

Abstract:

MDS matrices are of great significance in the design of block ciphers and hash functions. In the present paper, we investigate the problem of constructing MDS matrices which are both lightweight and low-latency. We propose a new method of constructing lightweight MDS matrices using circulant matrices which can be implemented efficiently in hardware. Furthermore, we provide circulant MDS matrices with as few bit XOR operations as possible for the classical dimensions 4 × 4, 8 × 8 over the space of linear transformations over finite field F42 . In contrast to previous constructions of MDS matrices, our constructions have achieved fewer XORs.

Keywords: Linear diffusion layer, circulant matrix, lightweight, MDS matrix.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1131221

References:

[1] Augot, D., Finiasz, M.: Direct construction of recursive MDS diffusion layers using shortened BCH codes. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS 8540, pp. 3-17, 2015.
[2] Augot, D., Finiasz, M.: Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions. In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, pages 1551-1555. IEEE, 2013.
[3] Barreto, P., Rijmen, V.: The Anubis Block Cipher. Submission to the NESSIE Project, 2000.
[4] Berger, T. P.: Construction of Recursive MDS Diffusion Layers from Gabidulin Codes. In INDOCRYPT, LNCS 8250, pages 274-285. 2013.
[5] Blaum, M., Roth, R. M.: On Lowest Density MDS Codes. IEEE Transactions on Information Theory 45(1), 46-59 (1999).
[6] Daemen, J., Knudsen, L. R., Rijmen, V.: The Block Cipher SQUARE. In Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 149-165. Springer, Heidelberg (1997).
[7] Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, 2002.
[8] Guo, J., Peyrin, T., Poschmann, A.: The PHOTON Family of Lightweight Hash Functions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 222-239. Springer, Heidelberg (2011).
[9] Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.: The LED Block Cipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 326-341. Springer, Heidelberg (2011).
[10] Gupta, K. C., Ray, I. G.: On Constructions of Involutory MDS Matrices. In AFRICACRYPT, pages 43-60, 2013.
[11] Gupta, K. C., Ray, I. G.: On constructions of MDS matrices from companion matrices for lightweight cryptography. In: Cuzzocrea, A., Kittl, C., Simos, D. E., Weippl, E., Xu, L. (eds.) CD-ARES Workshops 2013. LNCS, vol. 8128, pp. 29-43. Springer, Heidelberg (2013).
[12] Junod, P., Vaudenay, S.: Perfect Diffusion Primitives for Block Ciphers Building Effcient MDS Matrices. In: Handschuh, H., Hasan, M. A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 84-99. Springer, Heidelberg (2004).
[13] Khoo, K., Peyrin, T., Poschmann, A., Yap, H.: FOAM: Searching for Hardware Optimal SPN Structures and Components with a Fair Comparison. In Cryptographic Hardware and Embedded Systems CHES 2014, volume 8731 of Lecture Notes in Computer Science, pages 433-450. Springer Berlin Heidelberg, 2014.
[14] Li, Y., Wang, M.: On the construction of lightweight circulant involutory MDS matrices. In: Thomas, P. (ed.): FSE 2016, LNCS 9783, pp. 121-139. Springer, Heidelberg (2016).
[15] MacWilliams, F. J., Sloane, N. J. A.: The Theory of Error-Correcting Codes. North-Holland Publishing Company, 2nd edition (1986).
[16] Sajadieh, M., Dakhilalian, M., Mala, H., Sepehrdad, P.: Recursive Diffusion Layers for Block Ciphers and Hash Functions. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 385-401. Springer, Heidelberg (2012).
[17] Shirai, T., Shibutani, K., Akishita, T., Moriai, S., Iwata, T.: The 128-Bit Blockcipher CLEFIA (Extended Abstract). In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 181195. Springer, Heidelberg (2007).
[18] Sim, S.M., Khoo, K., Oggier, F., Peyrin, T.: Lightweight MDS Involution Matrices. In: Leander, G., Demirci, H. (eds.) FSE 2015. LNCS, Springer (2015).
[19] Wu, S.,Wang, M.,Wu,W.: Recursive Diffusion Layers for (Lightweight) Block Ciphers and Hash Functions. In: L.R. Knudsen and H. Wu (eds.): SAC 2012, LNCS 7707, pp. 355-371, 2013.