Some methods for constructing MDS-matrices over finite field

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

Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 5-18

Résumé

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.

Détail

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

Bibliographie

[1] Shannon C. E., “Communication theory of secrecy systems”, Bell System Technical J., 28:4 (1949), 656–715 | DOI | MR | Zbl

[2] Augot D., Finiasz M., “Direct construction of recursive MDS diffusion layers using shortened BCH codes”, Intern. Workshop on Fast Software Encryption, Springer, 2014, 3–17

[3] Guo J., Peyrin T., Poschmann A., “The PHOTON family of lightweight hash functions”, Ann. Cryptology Conf., Springer, 2011, 222–239 | Zbl

[4] Gupta K. C., Ray I. G., “On constructions of MDS matrices from companion matrices for lightweight cryptography”, Intern. Conf. Availability, Reliability, and Security, Springer, 2013, 29–43

[5] Sarkar S., Sim S. M., “A deeper understanding of the XOR count distribution in the context of lightweight cryptography”, Intern. Conf. Cryptology in Africa, Springer, 2016, 167–182 | MR | Zbl

[6] Toh D., Teo J., Khoo K., Sim S. M., “Lightweight MDS serial-type matrices with minimal fixed XOR count”, Intern. Conf. Cryptology in Africa, Springer, 2018, 51–71 | MR | Zbl

[7] Burov D. A., Pogorelov B. A., “The influence of linear mapping reducibility on the choice of round constants”, Matematicheskie Voprosy Kriptografii, 8:2 (2017), 51–64 | DOI | MR

[8] Glukhov M. M., Elizarov V. P., Nechaev A. A., Algebra, Lan Publ., St. Petersburg–Moscow–Krasnodar, 2015 (in Russian)