Muharrem Tolga SAKALLI, Sedat AKLEYLEK, Kemal AKKANAT, Vincent RIJMEN

On the automorphisms and isomorphisms of MDS matrices and their efficient implementations

In this paper, we explicitly define the automorphisms of MDS matrices over the same binary extension field. By extending this idea, we present the isomorphisms between MDS matrices over F2m and MDS matrices over F2mt , where t ≥ 1 and m > 1, which preserves the software implementation properties in view of XOR operations and table lookups of any given MDS matrix over F2m . Then we propose a novel method to obtain distinct functions related to these automorphisms and isomorphisms to be used in generating isomorphic MDS matrices new MDS matrices in view of implementation properties using the existing ones. The comparison with the MDS matrices used in AES, ANUBIS, and subfield-Hadamard construction shows that we generate an involutory 4 × 4 MDS matrix over F28 from an involutory 4 × 4 MDS matrix over F24 whose required number of XOR operations is the same as that of ANUBIS and the subfield-Hadamard construction, and better than that of AES. The proposed method, due to its ground field structure, is intended to be a complementary method for the current construction methods in the literature.

Keywords:

MDS matrix, branch number, block cipher,

PDF

___

[1] Shannon CE. Communication theory of secrecy systems. Bell System Technical Journal 1949; 28: 656-715. doi: 10.1002/j.1538-7305.1949.tb00928.x
[2] Daemen J, Rijmen V. The Design of Rijndael, AES - The Advanced Encryption Standard. Berlin, Germany: Springer-Verlag, 2002.
[3] Barreto PSLM, Rijmen V. Whirlpool. In: van Tilborg HCA, Jajodia S. (editors). Encyclopedia of Cryptography and Security. 2nd ed. Boston, MA, USA: Springer, 2011, pp. 1384-1385.
[4] Guo J, Peyrin T, Poschmann A. The PHOTON family of lightweight hash functions. In: Proceedings of CRYPTO; Santa Barbara, CA, USA; 2011. pp. 222-239.
[5] Barreto PSLM, Nikov V, Nikova S, Rijmen V, Tischhauser E. Whirlwind: A new cryptographic hash function. Design, Codes and Cryptography 2010; 56: 141–162. doi: 10.1007/s10623-010-9391-y
[6] Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems. In: Proceedings of CRYPTO; Santa Barbara, CA, USA; 1990. pp. 2-21.
[7] Matsui M. Linear cryptanalysis method for DES cipher. In: Proceedings of EUROCRYPT; Lofthus, Norway; 1993. pp. 386-397.
[8] Youssef AM, Mister S, Tavares SE. On the design of linear transformation for substitution permutation encryption networks. In: Proceedings of SAC; Ottowa, Canada; 1997. pp. 40-48.
[9] Gupta KC, Ray IG. On constructions of circulant MDS matrices for lightweight cryptography. In: Proceedings of ISPEC; Fuzhou, China; 2014. pp. 564-576.
[10] Lacan J, Fimes J. Systematic MDS erasure codes based on Vandermonde matrices. IEEE Transactions on Communications Letters 2004; 8 (9): 570-572. doi: 10.1109/LCOMM.2004.833807
[11] Sajadieh M, Dakhilalian M, Mala H, Omoomi B. On construction of involutory MDS matrices from Vandermonde matrices in GF(2q ). Design, Codes and Cryptography 2012; 64 (3): 287-308. doi: 10.1007/s10623-011-9578-x
[12] Augot D, Finiasz M. Direct construction of recursive MDS diffusion layers using shortened BCH codes. In: Proceedings of FSE; London, UK; 2014. pp. 3-17.
[13] Berger TP. Construction of recursive MDS diffusion layers from Gabidulin codes. In: Proceedings of INDOCRYPT; Mumbai, India; 2013. pp. 274-285.
[14] Cauchois V, Loidreau P, Merkiche N. Direct construction of quasi-involutory recursive-like MDS matrices from 2- cyclic codes. IACR Transactions on Symmetric Cryptology 2016; 2016 (2): 80-98. doi: 10.13154/tosc.v2016.i2.80-98
[15] Sajadieh M, Dakhilalian M, Mala H, Sepehrdad P. Recursive diffusion layers for block ciphers and hash functions. In: Proceedings of FSE; Washington, DC, USA; 2012. pp. 385-401.
[16] Wu S, Wang M, Wu W. Recursive diffusion layers for (lightweight) block ciphers and hash functions. In: Proceedings of SAC; Windsor, Canada; 2012. pp. 355-371.
[17] Sim SM, Khoo K, Oggier F, Peyrin T. Lightweight MDS involution matrices. In: Proceedings of FSE; İstanbul, Turkey; 2015. pp. 471-493.
[18] Li Y, Wang M. On the construction of lightweight circulant involutory MDS matrices. In: Proceedings of FSE; Bochum, Germany; 2016. pp. 121-139.
[19] Liu M, Siu SM. Lightweight MDS generalized circulant matrices. In: Proceedings of FSE; Bochum, Germany; 2016. pp. 101-120.
[20] Pehlivanoğlu MK, Sakallı MT, Akleylek S, Duru N, Rijmen V. Generalisation of Hadamard matrix to generate involutory MDS matrices for lightweight cryptography. IET Information Security 2018; 12 (4): 348-355. doi: 10.1049/iet-ifs.2017.0156
[21] Jean J, Peyrin T, Sim SM, Tourteaux J. Optimizing implementations of lightweight building blocks. IACR Transactions on Symmetric Cryptology 2017; 2017 (4): 130–168. doi: 10.13154/tosc.v2017.i4.130-168
[22] Güzel GG, Sakallı MT, Akleylek S, Rijmen V, Çengellenmiş Y. A new matrix form to generate all 3 × 3 involutory MDS matrices over F2m . Information Processing Letters 2019; 147: 61-68. doi: 10.1016/j.ipl.2019.02.013
[23] Kranz H, Leander G, Stoffelen K, Wiemer F. Shorter linear straight-line programs for MDS matrices. IACR Transactions on Symmetric Cryptology 2017; 2017 (4): 188-211. doi: 10.13154/tosc.v2017.i4.188-211
[24] Sarkar S, Syed H. Lightweight diffusion layer: importance of Toeplitz matrices. IACR Transactions on Symmetric Cryptology 2016; 2016 (1): 95-113. doi: 10.13154/tosc.v2016.i1.95-113
[25] Choy J, Yap H, Khoo K, Guo J, Peyrin T et al. SPN-Hash: improving the provable resistance against differential collision attacks. In: Proceedings of AFRICACRYPT; Ifrane, Morocco; 2012. pp. 270-286.
[26] MacWilliams FJ. Combinatorial properties of elementary abelian groups. PhD, Radcliffe College, Cambridge, UK, 1962.
[27] Bonneau PGA. Codes et combinatoire. PhD, Université Pierre et Marie Curie, Paris, France, 1984 (in French).
[28] Buchmann J, Pyshkin A, Weinmann RP. Block ciphers sensitive to Gröbner basis attacks. In: Proceedings of CT-RSA; San Jose, CA, USA; 2006. pp. 313-331.
[29] Barreto PSLM, Rijmen V. The Anubis block cipher. In: First Open NESSIE Workshop, KU-Leuven, Belgium; 2000.
[30] MacWilliams FJ, Sloane NJA. The Theory of Error Correcting Codes. Amsterdam, the Netherlands: North Holland, 1986.
[31] Lidl R, Niederreiter H. Introduction to Finite Fields and Their Applications. Cambridge, UK: Cambridge University Press, 1986.
[32] Barreto PSLM, Rijmen V. The Khazad legacy-level block cipher. In: First Open NESSIE Workshop, KU-Leuven, Belgium; 2000.
[33] Junod P, Vaudenay S. Perfect diffusion primitives for block ciphers. In: Proceedings of SAC; Waterloo, Canada; 2004. pp. 84-99.

Turkish Journal of Electrical Engineering and Computer Science-Cover

ISSN: 1300-0632
Yayın Aralığı: Yılda 6 Sayı
Yayıncı: TÜBİTAK

Arşiv