Applying Horner's Rule to Optimize Lightweight MDS Matrices

Applying Horner's Rule to Optimize Lightweight MDS Matrices

Jian Bai (Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China), Yao Sun (State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China), Ting Li (State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China) and Dingkang Wang (Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China)
Copyright: © 2019 |Pages: 15
DOI: 10.4018/IJDCF.2019100106

Abstract

This article is concerned with the problem of constructing lightweight MDS matrices. The authors present a new construction of 4 × 4 MDS matrices over GL(F2, m) for any integer m. They give sufficient and necessary conditions to determine whether the construction is an MDS matrix. Further, for any even number m ≥ 4, they construct lightweight MDS matrices in this structure. Applying Horner's rule to implement MDS matrices, the authors constructions need only 8+4×3×m XOR operations.
Article Preview
Top

1. Introduction

Diffusion and confusion are two fundamental properties that must be considered when designing symmetric-key ciphers (Shannon, 1949). These two properties are required for the security of the cipher. The diffusion layer is often obtained by a linear diffusion matrix. Matrices with higher branch number perform better to resist linear and differential attacks. The matrix with the maximum branch number is perfect for constructing diffusion layers and called a Maximal Distance Separable (MDS) matrix.

MDS matrices are widely used in many ciphers, including AES (Daemen &Rijmen, 2002), LED (Guo, Peyrin, & Poschmann, 2011) and SQUARE (Daemen, Knudsen, & Rijmen, 1997). When resources are limited, it is necessary to reduce the implementation costs when designing diffusion layers. For MDS matrices, the construction of lightweight MDS matrices becomes a hot topic, where lightweight MDS matrices means MDS matrices with small XOR counts.

The general method of constructing MDS matrices is based on the matrices with some specific structures. Since searching for all the MDS matrices is beyond the reach, when the dimension of the matrix increases. Circulant matrices and Hadamard matrices are preferred due to their limited number of different elements, which also leads to a smaller number of different minors. Circulant-like MDS matrices were constructed and the lightest MDS circulant-like matrices were found in (Junod & Vaudenay, 2005; Gupta & Ray, 2014). In 2014, Khoo et al. (Khoo, Peyrin, Poschmann, & Yap, 2014) introduced the metric XOR count that measures the implementation cost of a diffusion matrix. Based on this metric, there are a lot of works. Sarkar and Syed (Sarkar & Syed, 2016) gave theoretical constructions of Toeplitz MDS matrices and reported the minimum value of the XOR counts of 4 × 4 MDS matrices over IJDCF.2019100106.m01 and IJDCF.2019100106.m02, respectively. Li et al. (Li, Bai, Sun, & Wang, 2016) reported the minimum value of the XOR counts of 4 × 4 MDS matrices over IJDCF.2019100106.m03.

Another way for constructing lightweight MDS matrices is by recursive construction. This method was used in the design of PHOTON lightweight hash family (Guo, Peyrin, & Poschmann, 2011) and LED lightweight block cipher (Guo, Peyrin, Poschmann & Robshaw, 2011)for the first time. Sajadieh et al. (Sajadieh, Dakhilalian, Mala, & Sepehrdad, 2015) extended the recursive method by using linear transformations instead of multiplications of elements infinite fields. It helps to increase the choices of entries in MDS matrices. Then Wu et al. (Wu, Wang, & Wu, 2013) presented some extreme lightweight MDS matrices by using linear transformations with fewer XORs. Toh et al. (Toh, Teo, Khoo, & Sim, 2017) proposed a new class of serial-type matrices known as Diagonal Serial Invertible (DSI) matrices.

Recently, Beierle et al. (Beierle, Kranz, & Leander, 2016) and Jean et al. (Jean, Peyrin, Sim, & Tourteaux, 2017) proposed the s-metric to reduce the implementation cost of diffusion matrices. By finding a short linear straight-line program to the case of MDS matrices, Kranz et al. (Kranz, Leander, Stoffelen, & Wiemer, 2017) optimized the previous constructions globally. Their metric can be applied to any matrix and they found that MDS matrices of special types do not differ much for all randomized constructions.

Contributions. In this paper, we study the constructions of MDS matrices and present a new metric to reduce the implementation cost of MDS matrices.

First, we present a new structure to construct MDS matrices over IJDCF.2019100106.m04. Then we propose two conditions to construct MDS matrices and sufficient and necessary conditions under two different conditions are given.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 11: 4 Issues (2019)
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing