Geodesic
An algorithm for finding the minimum degree of~a~polynomial over~a~finite field for~a~function over~a~vector space depending on~the~choice of~an~irreducible polynomial
Prikladnaâ diskretnaâ matematika, no. 1 (2019), pp. 5-15.

Voir la notice de l'article provenant de la source Math-Net.Ru

The transformations of the vector space of $p$-ary vectors of length $n$, where $p$ is a prime number, are considered. Each such a transformation is assigned to a polynomial over a finite field $\mathrm{GF}(p^n)$. The finite field is represented by a residue ring modulo an irreducible polynomial. In general, depending on the choice of the irreducible polynomial, different polynomials over the finite field will correspond to the transformation over the vector space. In this paper, we propose an algorithm for finding the minimal degree of such a polynomial and an irreducible polynomial at which this degree is achieved. The algorithm is based on the calculation of expressions for polynomial coefficients through its values. In the process of the algorithm, the elements of finite fields are treated as polynomials. To compute specific irreducible polynomials, the Euclid algorithm computes the greatest common divisor of these expressions and the polynomial, which is the product of all irreducible polynomials of degree $n$. To work up to degree $d$, the algorithm requires storage of O$(p^nn)$ elements from GF$(p)$ and O$(p^nn^2d^4w)$ operations of addition and multiplication modulo $p$ where $w$ is the number of elements on which the polynomial is nonzero. Thus, the algorithm is especially effective for functions that have many zero values. The minimal degree polynomials for the S-boxes of block ciphers (GOST 28147-89, ICEBERG, LUFFA, LUCIFER, SERPENT, AES, PRESENT, GOST 34.12-2015) as well as the irreducible polynomials at which this degree is achieved have been computed.
Keywords: finite field, irreducible polynomial, Boolean functions, block cipher. 
@article{PDM_2019_1_a0,
     author = {S. A. Belov},
     title = {An algorithm for finding the minimum degree of~a~polynomial over~a~finite field for~a~function over~a~vector space depending on~the~choice of~an~irreducible polynomial},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {5--15},
     publisher = {mathdoc},
     number = {1},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_1_a0/}
}
TY  - JOUR
AU  - S. A. Belov
TI  - An algorithm for finding the minimum degree of~a~polynomial over~a~finite field for~a~function over~a~vector space depending on~the~choice of~an~irreducible polynomial
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 5
EP  - 15
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_1_a0/
LA  - ru
ID  - PDM_2019_1_a0
ER  - 
%0 Journal Article
%A S. A. Belov
%T An algorithm for finding the minimum degree of~a~polynomial over~a~finite field for~a~function over~a~vector space depending on~the~choice of~an~irreducible polynomial
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 5-15
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_1_a0/
%G ru
%F PDM_2019_1_a0
S. A. Belov. An algorithm for finding the minimum degree of~a~polynomial over~a~finite field for~a~function over~a~vector space depending on~the~choice of~an~irreducible polynomial. Prikladnaâ diskretnaâ matematika, no. 1 (2019), pp. 5-15. http://geodesic.mathdoc.fr/item/PDM_2019_1_a0/

[1] Youssef A. M., Gong G., “On the interpolation attacks on block ciphers”, Intern. Workshop on Fast Software Encryption, Berlin–Heidelberg, 2000, 109–120

[2] Lidl R., Niederreiter H., Finite Fields, v. 20, Cambridge University Press, Cambridge, 1997 | MR

[3] McWilliams F. J., Sloane N. J. A., The Theory of Error-Correcting Codes, Elsevier, N.Y., 1977 | MR

[4] Sorenson J., “An analysis of Lehmer's Euclidean GCD algorithm”, Proc. Intern. Symp. on Symbolic and Algebraic Computation (Montreal, Canada, 1995), 257–397

[5] Carlet C., “Boolean functions for cryptography and error correcting codes”, Boolean Models and Methods in Mathematics, Computer Science, and Engineering, eds. Y. Crama, P. Hammer, Cambridge University Press, Cambridge, 2010, 257–397 | DOI | MR | Zbl

[6] Jakobsen T., Knudsen L. R., “The interpolation attack on block ciphers”, Intern. Workshop on Fast Software Encryption, Springer, 1997, 28–40 | DOI | MR | Zbl

[7] GOST 28147-89. Information Processing Systems. Cryptographic Protection. Algorithm of Cryptographic Transformation, Standards Publ., M., 1989 (in Russian)

[8] Popov V., Kurepkin I., Leontiev S., RFC 4357: Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001 and GOST R 34.11-94 Algorithms, IETF, M., 2006

[9] Standaert F. X., Piret G., Rouvroy G., et al., “ICEBERG: An involutional cipher efficient for block encryption in reconfigurable hardware”, Intern. Workshop on Fast Software Encryption, Berlin–Heidelberg, 2004, 279–298 | DOI

[10] De Canniere C., Sato H., Watanabe D., Hash Function Luffa: Specification. Submission to NIST SHA-3 Competition, , 2008 http://www.hitachi.com/rd/yrl/crypto/luffa

[11] Sorkin A., “Lucifer, a cryptographic algorithm”, Cryptologia, 8:1 (1984), 22–42 | DOI

[12] Biham E., Anderson R., Knudsen L., “Serpent: A new block cipher proposal”, Intern. Workshop on Fast Software Encryption, Berlin–Heidelberg, 1998, 222–238 | DOI | MR | Zbl

[13] Daemen J., Rijmen V., The Design of Rijndael. AES — the Advanced Encryption Standard, Springer Science Business Media, Berlin–Heidelberg, 2013 | MR

[14] Bogdanov A., Knudsen L. R., Leander G., et al., “PRESENT: An ultra-lightweight block cipher”, Intern. Workshop on Cryptographic Hardware and Embedded Systems, Berlin–Heidelberg, 2007, 450–466 | Zbl

[15] Information Technology. Cryptographic Protection of Information. Block Ciphers, Standartinform Publ., M., 2015 (in Russian)