Theoretical Backgrounds of Applied Discrete Mathematics

Some methods for constructing MDS-matrices over finite field

O. Coy Puente, R. A. De La Cruz Jiménez

Certification Research Center, Moscow, Russia

Abstract: In this work, we propose new methods for constructing MDS-matrices over finite field by using recursive ones. For some element $\beta \in \text{GF}(2^ n)$ and naturals numbers $s$ and $k$, we study polynomials of the form $x^4 + \beta^k x^3 + \beta x^2 + \beta^k x + 1$ and $x^6 + \beta^s x^5 + \beta^2 x^4 + \beta x^3 + \beta^2 x^2 + \beta^s x+1$, for which, when $t=4,6$, the $t$-th power of it's companion matrices yields MDS-matrices with irreducible characteristic polynomial. Also, for some finite field elements $\beta$ and $\gamma$, we have found MDS-matrices of the form $\mathcal{M}^4_{(\beta,\gamma)}=(\beta\cdot\mathcal{I}_{4,4}\oplus \gamma\cdot\mathcal{J}_{4,4} \oplus\mathcal{H}_{4,4})^4$, where for appropriate ($4\times 4$)-binary matrices $\mathcal{I}_{4,4},\mathcal{J}_{4,4},\mathcal{H}_{4,4}$ the resulting linear mappings can be simplified by some special schemes, very attractive for the so-called lightweight cryptography. The multiplication of any vector by the matrices obtained in the paper can be represented by some circuits which improve the cost of this operation implementation in terms of bitwise XOR's.

Keywords: MDS-matrices, companion matrices, irreducible polynomials, LFSR, finite field, lightweight cryptography, XOR-count.

UDC: 621.391:519.7+621.391.1:004.7

DOI: 10.17223/20710410/46/1

Bibliographic databases:

•