On the Construction of Lightweight Circulant Maximum Distance Separable Matrices

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.

Authors:

• Qinyi Mei
• Li-Ping Wang

Keywords:

• Linear diffusion layer
• circulant matrix
• lightweight
• MDS matrix.

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.